Official

C - Piles of Pebbles Editorial by evima


Let \(B_i\) be the remainder when \(A_i\) is divided by \(X+Y\). Below, we call Takahashi and Aoki the first and second players, respectively.

First, if all \(B_i\) are less than \(X\), the second player wins. This is because for each pile chosen by the first player, the value of \(B_i\) becomes at least \(Y\), so the second player can choose the same piles to restore the previous values of \(B_i\).

Next, assume \(X \leq Y\). If there is some \(B_i\) greater than or equal to \(X\), the first player wins. This is because he can choose the piles whose \(B_i\) are greater than or equal to \(X\) in his operation so that all \(B_i\) are less than \(Y\).

Finally, consider the case \(X>Y\). Here, none of the piles whose \(B_i\) are less than \(X\) can be chosen, while all of the piles whose \(B_i\) are greater than or equal to \(X\) must be chosen. This uniquely specifies the set of piles to choose, and the outcome of the game can be determined from the arguments in the previous cases.

posted:
last update: