Fibonacci Game
Time limit2sMemory limit128 MB
Determine the smallest first move in a Fibonacci-Nim-like bead-taking game that guarantees a forced win, or -1 if none exists.
- Level
Medium6 of 10
- Topics
- Game theory, Number theory, Math
- Solved
- No attempts yet
Problem
There are N beads. Two players alternately take beads, and the player who takes the last bead wins.
Player 1 moves first. On the first move, Player 1 may take at least 1 and at most N-1 beads, so taking all beads is not allowed. From then on, a player may take at most twice as many beads as the opponent took on the immediately previous move. For example, if the opponent just took 1 bead, the current player may take 1 or 2 beads.
If N = 3, no matter how Player 1 starts, Player 2 can take all remaining beads. If N = 4, Player 1 can win by taking 1 bead first.
Determine how many beads Player 1 should take on the first move in order to win. If several first moves are winning, output the smallest such number. If every possible first move loses, output -1.
Input
The first line contains an integer N.
- 2 <= N <= 1,000,000
Output
Output the number of beads Player 1 should take on the first move. If no winning first move exists, output -1.