### PROBLEM LINKS :

## Practice

## Contest

**Author** and **Editorialist** Vineet Paliwal

**Tester** Roman Rubanenko

# DIFFICULTY :

## Easy-Medium

# PREREQUISITES :

## Basic Game Theory , Zero-sum game , Impartial game , Sprague Grundy Theorem .

# PROBLEM :

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 .

# EXPLANATION:

### 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 .

### Explanation :

Subtask 1 and 2 can be solved with Basic game theory .

For subtask 3 apply Sprague Grundy Theorem .