Fun Isolation
Limits: 1 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka finally went on a foreign trip. Due to the burdock virus, they have to spend a whole week in a hotel in isolation. To somehow entertain themselves, they decided to play one of their favorite games.
Initially, there is an array of length \(n\), consisting of numbers 0 and 1. Marichka and Zenyk take turns. Zenyk goes first. On his turn, a player can choose any subarray with an even sum and replace all its elements with zeros, or choose any subarray with an odd sum and replace all elements with ones.
Zenyk wins if at some point all elements of the array are zeros, and Marichka wins if they are ones.
Can you determine who wins if both players play optimally?
Input
The first line contains an integer \(n\) — the length of the array.
The second line contains \(n\) space-separated integers, each of which is 0 or 1.
Output
Print Zenyk if Zenyk wins with optimal play, or
Marichka — otherwise.
Constraints
\(1 \le n \le 10^5\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 0 1 0 | Zenyk |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 0 1 1 | Marichka |
Notes
In the first example, Zenyk can win on the first move, because the sum of the entire array is even.
In the second example, no matter what move Zenyk chooses, Marichka wins: Zenyk can either make all elements equal to 1 and lose immediately, or make the sum of the entire array odd, after which Marichka wins on her turn.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Fun Isolation - Editorial
If the sum of all elements of the array is even, Zenyk wins with his first move. Otherwise, if Zenyk leaves the sum odd, Marichka wins with her next move. To avoid this, Zenyk must change the parity of the sum of the array with his move. The only way to do this is to take some segment of even length with an odd sum and replace all its elements with ones. Then the sum of all elements changes from odd to even. This is the only way for Zenyk to avoid losing immediately after Marichka’s next move.
Note that with such a move Zenyk increases the number of ones in the array. If Marichka follows the same strategy, the number of ones increases after every move, so sooner or later all elements become ones, and Marichka wins. That is, whatever his moves, Zenyk has no chance of winning.
So the winner is determined by the parity of the sum of all elements of the array.
Complexity: \(O(n)\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|