P8174 [CEOI 2021] Stones

Translated from CEOI 2021 Day 2 T1. [Stones](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf).

Ankica finally catches Branko, but he refuses to buy Ankica a newspaper and asks to come up with a new game because the previous one was unfair. Ankica pretends to be innocent and suggests another stone game, but Branko is suspicious and decides to completely change its rules. The game has $N$ piles of stones. The $i$-th pile contains $a_i$ stones. The players take turns removing some stones from one pile, and the player who takes the last stone wins. However, in this game, which pile a player must take stones from is fixed by the other player. More precisely, the turn number starts from $1$ and increases by $1$ each time, and the game proceeds as follows: - On odd-numbered turns, Branko specifies a non-empty pile. Ankica removes at least one stone and at most all stones from that pile. - On even-numbered turns, Ankica specifies a non-empty pile. Branko removes at least one stone and at most all stones from that pile. As a professional game player, after Branko sets up the piles, Ankica quickly realizes that she has a winning strategy in this game. If you are Ankica, can you win? #### Interaction This is an interactive problem. Your program must exchange information with the official program that plays Branko. Of course, your program should play the role of Ankica and ensure that she wins. Your program should first read the initial state of the game from standard input. The initial state has two lines: the first line contains an integer $N$, and the second line contains $N$ space-separated integers, where the $i$-th one is $a_i$, as described above. Depending on whether the current turn is odd or even, your program should behave differently: **On odd turns:** - Your program should first read an integer $k$. If all piles are empty at this moment, then $k=-1$, and you should terminate because you have lost. Otherwise, $k\in[1,N]$, meaning you must remove stones from pile $k$, at least one and at most all stones. It is guaranteed that pile $k$ is non-empty at this moment. Let pile $k$ currently contain $s_k$ stones. - Your program should output one integer in $[1,s_k]$, which is the number of stones you want to remove from pile $k$, **then flush the buffer**. **On even turns:** - Your program should first output an integer $k$, **then flush the buffer**. If all piles are empty at this moment, then $k$ should be $-1$, and you should terminate because you have won. Otherwise, $k\in[1,N]$, meaning you want Branko to remove stones from pile $k$. You should ensure that pile $k$ is non-empty at this moment. Let pile $k$ currently contain $s_k$ stones. - Your program should read one integer in $[1,s_k]$, which is the number of stones Branko removes from pile $k$. It is guaranteed that the given initial state allows you to have a winning strategy no matter how Branko plays. #### Interactive Sample 1 | Output | Input | Explanation | | :---------: | :------------: | :-----------------------------------: | | | $\texttt{1}$ | There is only one pile. | | | $\texttt{4}$ | This pile contains $4$ stones. | | | $\texttt{1}$ | Branko can only force Ankica to take from pile $1$. | | $\texttt{4}$ | | Ankica takes all stones from pile $1$. | | $\texttt{-1}$ | | Now there are no stones left, Ankica wins. | #### Interactive Sample 2 | Output | Input | Explanation | | :-----------: | :--------------: | :------------------------------------------: | | | $\texttt{3}$ | There are three piles. | | | $\texttt{1 1 5}$ | The three piles contain $1,1,5$ stones. | | | $\texttt{3}$ | Branko forces Ankica to take from pile $3$. | | $\texttt{5}$ | | Ankica takes all stones from pile $3$. | | $\texttt{1}$ | | Ankica forces Branko to take from pile $1$. | | | $\texttt{1}$ | Branko can only take all stones from pile $1$. | | | $\texttt{2}$ | Branko forces Ankica to take from pile $2$. | | $\texttt{1}$ | | Ankica takes all stones from pile $2$. | | $\texttt{-1}$ | | Now there are no stones left, Ankica wins. |

N/A

N/A

#### Subtasks Let $M=\max\{a_1,a_2,\dots,a_N\}$. All test points satisfy $1\leq N,M\leq 500$. The constraints for each subtask are as follows: | Subtask | Score | Constraints | | :-----: | :---: | :------------------------------------------: | | $1$ | $12$ | $1\leq N,M\leq 7$ | | $2$ | $13$ | $1\leq N\leq 12$, $1\leq M\leq 500$ | | $3$ | $15$ | $1\leq N,M\leq 500$, and $\forall i,j\in[1,N],a_i=a_j$ | | $4$ | $60$ | $1\leq N,M\leq 500$ | Translated by ChatGPT 5