Subtask 1

In this subtask, every pile initially contains one stone. This means that once a pile is chosen, it will immediately become empty on the same turn. This means that the game will end after exactly ~N~ turns. Thus, Josh wins if ~N~ is odd, and Mike wins if ~N~ is even.

Time Complexity: ~\mathcal{O}(\sum N)~

Subtask 2

In this subtask, every pile initially has the same amount of stones. We already know from subtask ~1~ that if all piles initially contain one stone, then Josh wins if and only if ~N~ is odd.

Otherwise, if every pile initialy has more than one stone, we can show that Mike is always the winner. Mike can use the following strategy to force a win:

• When Josh chooses pile ~i~, Mike should remove ~(a_i - 1)~ stones such that there is only one stone left in the pile.
• Then, on Mike's following turn, he should choose the same pile. Josh will be forced to remove the only remaining stone in the pile, making it empty.

Eventually, Josh will run out of piles to choose, and he will lose.

Time Complexity: ~\mathcal{O}(\sum N)~

Subtask 3

This is a game theory problem, which motivates us to think about winning and losing states.

Our goal is to find a characterization of states as winning or losing. As with many problems, a good way to start is to consider a simpler version of the problem; in this case, let's assume there are only piles with one or two stones, and later try to generalise our argument.

The second game of the sample output gives a nice strategy; if there is exactly one pile with one stone, and every other pile has two stones, then Josh can force a win as described by the sample explanation.

Now, consider a game with two piles with one stone, with every other pile containing two stones. If Josh chooses a pile with one stone, then after Josh's turn, the state of the game will be as described in the previous paragraph, so Mike will be able to win. If Josh chooses a pile with two stones, then Mike can reduce the pile to one stone. On Mike's next turn, he can then choose the same pile, forcing Josh to empty the pile. This process can be repeated until Josh chooses a pile with one stone, in which case Mike can force a win. Therefore, Mike will win in this scenario.

Now, consider a game with three piles with one stone, with every other pile containing two stones. We can apply exactly the same logic as before to determine that Josh will win. In general, we see that Josh wins if and only if the number of piles initially containing one stone is odd.

But wait! Our argument for the simplified problem only depends on whether piles contain one stone or more than one stone. So, it seems promising to guess that in the generalised problem, Josh wins if the number of piles initially containing exactly one stone is odd.

In a contest setting, this intuition is enough for an AC. But we can formalise the argument in terms of winning and losing states.

Let ~X~ be the number of piles currently containing one stone. We need to show that when ~X~ is odd, the current state is winning, and if ~X~ is even, the current state is losing. In particular, we need to show that all winning states can be forced to becoming a losing state after one turn, and any losing state can be forced into becoming a winning state after one turn. Using our previous argument:

• If ~X~ is odd, then the current state is winning. Since ~X~ must be positive, the current player must be able to select a pile with exactly one stone, forcing their opponent to remove the remaining stone. After this turn, ~X~ decreases by one, so it must become even: a losing state.
• If ~X~ is even, then the current state is losing. If the current player selects a pile with one stone, then their opponent will clear the pile, reducing ~X~ by one and resulting in a winning state. Otherwise, if the current player selects a pile with more than one stone, then their opponent can remove stones such that there is only one stone left in the pile, increasing ~X~ by one and resulting in a winning state.

Of course, the state where all piles are empty has ~X = 0~, and is classified as a losing state (as expected). This is enough to show that Josh wins if and only if there is an odd number of piles initially containing one stone.

Time Complexity: ~\mathcal{O}(\sum N)~