P6487 [COCI 2010/2011 #4] HRPA

There are $n$ stones. Two players play the game with the following rules: - Mirko takes once first, then Slavko takes once, then Mirko takes once again. They take turns taking stones, and so on. - On Mirko’s first move, he may take any positive number of stones. - After that, on each move, the player must take at least one stone and at most $2$ times the number taken in the previous move. Of course, the number taken must not exceed the number of stones currently remaining on the table. - The player who takes the last stone wins. Both players play optimally. Mirko wants to know the minimum number of stones he must take on his first move in order to win in the end.

One line containing one integer $n$, the number of stones.

One line containing one integer, the minimum number of stones Mirko must take to guarantee a win.

#### Explanation of Sample 1 For this sample, Mirko can take $1/2/3/4$ stones on his first move. Although taking $4$ stones would win the game immediately, it is not the minimum. The minimum strategy is to take $1$ stone. Then Slavko can only take $1$ or $2$ stones. No matter which one he chooses, Mirko can take all remaining stones on the next move and win. #### Constraints For $100\%$ of the testdata, it is guaranteed that $2\le n\le 10^{15}$. #### Note **Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T6 HRPA***。 Translated by ChatGPT 5