Problem Description
Barr the Bear and Poe the Penguin like to play games with each other. Today, they took a bag of N
pebbles and agreed that they would play by the following rules
- Poe the Penguin would move first since Barr the Bear was lazy.
- Poe the Penguin can take any number of stones (from 1 to N) from the bag of stones during
this first move.
- In each of the following moves the current player must take at least 1 stone from the bag, and
he can take up to double the number of stones taken during the previous turn. Obviously, he
cannot take more stones than there are in the bag.
- The player who takes the last stone is the winner, and gets treated to a free lunch.
If both Poe the Penguin and Barr the Bear played optimally, Poe the Penguin would always get the
free lunch. To mock Barr the Bear, Poe the Penguin would like to know the minimum number of
stones he must take on his first turn to guarantee a win given optimal play by both sides.
Input
The input contains a single integer N, which denotes the number of stones initially in the bag.
Output
Output the minimum number of stones Poe the Penguin would need to remove on his first turn so
that he could still win given optimal play by both sides.
Subtask 1 (20 points)
1 ≤ N ≤ 100.
Subtask 2 (30 points)
1 ≤ N ≤ 1,000
Subtask 3 (50 points)
1 ≤ N ≤ 10
9
Acknowledgements
Taken from Chuanqi's 2012 IOI Training Contest 1 with limits reduced.
Sample Input 1
4
Sample Output 1
1
Explanation for Sample Output 1
After removing one stone on his first turn, Poe the Penguin can remove the remaining
stones no matter what Barr the Bear plays.
Sample Input 2
7
Sample Output 2
2
Explanation for Sample Output 1
Poe the Penguin removes 2 stones on his first turn. If Barr the Bear removes more than
1 stone on his turn, then Poe the Penguin can remove all remaining stones and win. If Barr the Bear
removes a single stone, then Poe the Penguin removes a single stone on his turn again. No matter
what Barr the Bear does now, Poe the Penguin is able to remove all remaining stones and win.