Split Game
Time limit2sMemory limit512 MB
Given piles of tokens, players alternately split one pile into copies of some smaller size K; decide the winner under optimal play.
- Level
Medium7 of 10
- Topics
- Game theory, Dynamic programming, Math, Implementation
- Solved
- No attempts yet
Problem
For a long time, the rich clientele of Binary Casino has been asking for a new way to gamble their money. To grant their wish, the director of Binary Casino decided to introduce a new game called Split Your Tokens.
The game is played only when a customer is about to leave the casino. Instead of exchanging the tokens won during the visit, the customer may accept the casino's challenge and bet all of the tokens he has won on the outcome of this game. If the customer loses, he loses all of his tokens, which go to the casino.
When the game starts, the customer splits his tokens into N piles, which do not need to hold the same number of tokens. The customer and the casino then take turns. In this game the customer is called the first player and the casino the second player. On his turn, each player decides which pile to split and chooses a positive integer K smaller than the size of the chosen pile. The player then splits that pile into as many piles of size K as possible. If any tokens remain, they form one more pile of their own. A player loses the game when he cannot split any more. The customer (the first player) always moves first.
The director of Binary Casino is not sure whether this game will be profitable for the casino in the long run. Your task is to determine, for a given configuration of piles, which player wins when both players play optimally.
Input
The first line contains one integer N (1 ≤ N ≤ 2000), the number of piles. The second line contains N integers Pi (1 ≤ Pi ≤ 2000), where Pi is the number of tokens in the i-th pile.
Output
Output a single line with either “First” or “Second”, depending on which player wins when both play optimally.