PROBLEM LINKS :
Basic Game Theory , Zero-sum game , Impartial game , Sprague Grundy Theorem .
Given n piles of stones . In each turn you can remove a^a stones for some natural number a from one of the piles . Given two players
who alternately play their moves , the loser is the one who is unable to make a move. Given an initial configuration you have to predict the winner under the assumption of optimal play .
Basic game theory Concept :
In case there is no pile of stones at all the first player loses . In case there are only a few piles , the problem can be solved iteratively .
The base state is when there are 0 stones in all the piles , when the first player loses . For all other states , the state is win for first player if a state which is win for the second player is reachable from it in one move otherwise it is a losing position .
Example : Suppose we have only 1 pile with N stones .
N = 0 : Second win ( base case )
N = 1 : N = 0 is reachable which is second win , hence this position is first win .
N = 2 : N = 1 is reachable , which is first win , hence this position is second win .
N = 3 : N = 2 is reachable , which is second win , hence this position is first win .
N = 4 : N = 3 and N = 0 are reachable , N = 0 is second win , hence this position is first win .
( Note only one of the positions reachable being second win is sufficient for the position to be first win ) .
N = 5 : N = 4 and N = 1 are reachable , N = 1 is first win and N = 4 is first win, hence this position is second win .
( Note when all reachable positions are first win , then the position is second win )
Sprague Grundy Theorem :
We associate with each position of the game a number called the Grundy number of the position .
The Grundy number of a losing position is 0 . Any other value of grundy number denotes a winning position .
The grundy number of the position is the smallest number which is not a grundy number of the position reachable from it .
The grundy number of a combination of games is the xor of grundy numbers of all the games .
Subtask 1 and 2 can be solved with Basic game theory .
For subtask 3 apply Sprague Grundy Theorem .