Coin Tower Game
Time limit1sMemory limit512 MB
Two players take coins from two towers, and the one who takes the last coin gains or loses K coins. Find whether Yeongdo should move first or second to win.
- Level
Medium7 of 10
- Topics
- Game theory, Dynamic programming
- Solved
- No attempts yet
Problem
The coin tower game is played by two players, each with two towers of and coins. The players take turns. On each turn, a player picks one non-empty tower and takes at least one coin from it. When no coins are left to take, the game ends and the player who took more coins wins. If both players took the same number of coins, the second player wins.
Mingyu wanted to make this simple game more interesting. So he chose an integer , so that the outcome stays unknown until the game ends, and added this rule for the player who takes the last coin.
- If is a non-negative integer, that player gains extra coins.
- If is negative, that player loses coins. If the player has fewer than coins, that player loses the game.
Mingyu plays this improved game with Yeongdo. Yeongdo spotted the winning strategy as soon as he saw the game, and quickly took the choice of going first or second. Assuming both players play optimally, should Yeongdo choose to go first or second in order to win?
Input
The first line contains , , and , separated by spaces.
Output
If Yeongdo should go first, print "First". If he should go second, print "Second".
Constraints
- All numbers in the input are integers.