AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

FPC21-007.Coatis and Owls

Easy · 1 s · 256 MB

  • icpc
  • fpc
  • 2021

The coatis and owls have been at war for a long time already. They are preparing for battle, but given the pandemic, they also want to comply to social distancing. Therefore, they decide to do a digital battle instead, by playing the game Furious Pikemen Combat (FPC) against each other.

The game features a one-dimensional battlefield. Both players control an army, each consisting of multiple squads of pikemen. The coati army is positioned on the left and the owl army is positioned on the right. During the game, the coati army walks to the right while the owl army walks to the left. When two enemy squads meet, they fight until one of the squads is completely defeated. Since all pikemen are equal in strength, the smaller squad will lose all of its pikemen. The winning squad will lose a number of pikemen depending on the size of the winning squad (www) and the size of the losing squad (lll), equal to ⌈l2/w⌉\left\lceil l^2 / w \right\rceil⌈l2/w⌉ (where ⌈x⌉\lceil x \rceil⌈x⌉ denotes rounding xxx up to the nearest integer, or ceiling). If two squads are equal in size, they will fight until both squads are annihilated.

Consider the first sample input as an example. The two squads controlled by the coatis (of 202020 pikemen) walk to the right and the squad controlled by the owls (of 333333 pikemen) walks to the left. When the right-most coati squad meets the owl squad, the coati squad is completely destroyed, while the owl squad loses ⌈202/33⌉=13\left\lceil 20^2/33 \right\rceil = 13⌈202/33⌉=13 pikemen. In other words, the owl squad has 202020 pikemen left. The single remaining squad for both players then consists of exactly 202020 pikemen, so both squads will be annihilated, resulting in a stalemate.

Calculate who wins this digital battle of FPC, and how many pikemen the army of the winning player has left after the battle.

Giriş formatı

The input consists of:

• A line with two integers nnn and mmm (1≤n,m≤2⋅1051\leq n,m\leq 2\cdot 10^51≤n,m≤2⋅105), the number of squads controlled by the coatis and the owls, respectively.

• A line with n+mn + mn+m integers aaa (1≤a≤1041 \leq a \leq 10^41≤a≤104), where each aaa indicates the size of one squad of pikemen.

Çıxış formatı

If all pikemen from both armies are defeated, output “stalemate”.

If one player wins the battle, output:

• A line containing either “coatis” if the coatis win the battle, or “owls” if the owls win the battle.

• A line with the number of pikemen remaining in the army of the winning player.

Qeyd

\footnotetext{\scriptsize Screenshot from Age of Empires II: Definitive Edition. \textcopyright{} Microsoft Corporation. This screenshot was created under Microsoft's “Game Content Usage Rules” (https://www.xbox.com/en-us/developers/rules) using assets from Age of Empires II: Definitive Edition, and it is not endorsed by or affiliated with Microsoft. }

Source: Freshmen Programming Contest 2021 · Author: Maarten Sijm · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 2 of the 26 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

2 1
20 20 33

Çıxış #1

stalemate

Giriş #2

3 3
10 10 10 20 10 10

Çıxış #2

owls
19