1214 : square game
Time Limit: 1 Sec Memory Limit: 256 MB Submitted: 85 Solved: 17Description
The square game is a two play game played with \(n\) piles of stones. Each pile has a positive integer number of stones \(a_i\).
Two players take turns making move. In each move, the current player chooses one pile and remove one or more stones from the pile satisfying following rules: Use the pile of stones to pile a maximal square, remove the remain stones in the pile, then remove arbitrary number of rows of the square.
In other words, if the player choose a pile with \(m\) stones, then he could remove \((m-\lfloor\sqrt{m}\rfloor^2+k\lfloor\sqrt m\rfloor)\) stones from the pile.(\(0\le k\le\lfloor \sqrt m\rfloor\) and \(k\not=0\) if \(m=\lfloor\sqrt m\rfloor^2\)).
The game ends when every stones are removed. The winner is the player who remove the last stone.
Find the result of the game when both players play optimally.The square game is a two play game played with \(n\) piles of stones. Each pile has a positive integer number of stones \(a_i\).
Two players take turns making move. In each move, the current player chooses one pile and remove one or more stones from the pile satisfying following rules: Use the pile of stones to pile a maximal square, remove the remain stones in the pile, then remove arbitrary number of rows of the square.
In other words, if the player choose a pile with \(m\) stones, then he could remove \((m-\lfloor\sqrt{m}\rfloor^2+k\lfloor\sqrt m\rfloor)\) stones from the pile.(\(0\le k\le\lfloor \sqrt m\rfloor\) and \(k\not=0\) if \(m=\lfloor\sqrt m\rfloor^2\)).
The game ends when every stones are removed. The winner is the player who remove the last stone.
Find the result of the game when both players play optimally.
Input
The first line contains one integer \(n\) \((1 \leq n \leq 10^5)\), represents the number of piles.
The second line contains \(n\) integers \(a_1,a_2\ldots,a_n\) \((1 \leq a_i \leq 10^6)\), represent the number of stones in each piles.
Output
Output ‘’First’’ if the first player wins, otherwise ‘’Second’’.
Sample
2 3 3
Second