**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Udit Sanghi

**Tester:** Teja Vardhan Reddy

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

EASY

**PREREQUISITES**:

game theory basics

**PROBLEM**:

Two players are playing following game. Initially they’re given integer N. On each turn if N is even, the current player must divide it by 2, otherwise the player must increase or decrease N by 1. Player who made N equal to 0 wins the game. You’re the first player, you have to win the game or declare it’s impossible.

**EXPLANATION**:

Note that if we may calculate function win(x) which is equal to 1 if first player wins and 0 otherwise then it’s easy for us to make a strategy. If win(N)=0 we simply say that we lose and go to the next game. Otherwise if N is even we divide it by 2 and if N is odd we make a move to N-1 or N+1 whichever gives win(N')=0. Very naive implementation of win(x) looks like this:

```
bool win(int x) {
if(x == 0) {
return false;
} else if(x == 1) {
return true;
} else {
if(x % 2 == 0) {
return !win(x / 2);
} else {
return !win(x - 1) | !win(x + 1);
}
}
}
```

If you’ll look on values of win(x) for small x, you may notice that it’s equal to 1 when x is odd.

Let’s prove it by induction. It holds for x=1. Now if last two bits are 11, you should subtract 1 and you’ll get odd number in return from other player’s move. Otherwise if last two bits are 01, you should add 1 and again you’ll get odd number in return from other player’s move. But in both cases it will be smaller odd number, thus it will be winning due to induction assumption. Thus win(x) is actually depends only on parity of the number of trailing zeroes of x and may be calculated e.

**ALTERNATIVE SOLUTION**:

Turns out you may simply add memoization to win(x) function and it would be enough to get AC! It seems that number of states you’ll visit may be estimated as 2 \log_2 n but rigorous proof is left to reader as an exercise

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.