No.2619 Sorted Nim
startcpp
KazunProblem Statement
There are piles $1, 2, \cdots, N$, and pile $i$ contains $A_i$ stones.
Initially, $A_1 \le \cdots \le A_N$ holds.
$2$ players play a stone-taking game. The first player and the second player alternately perform the following operation.
・Choose $1$ pile containing $1$ or more stones, and take $1$ or more stones from the chosen pile.
However, letting $a_i$ be the number of stones in pile $i$, only operations that keep $0 \le a_1 \le a_2 \le \cdots \le a_N$ can be performed.
For example, when the piles contain $3, 4, 6$ stones, one of the following can be performed:
- Choose pile $1$ and take $1, 2, 3$ stones
- Choose pile $2$ and take $1$ stone
- Choose pile $3$ and take $1, 2$ stones
The player who first becomes unable to perform an operation loses, and the other player wins.
When both players play optimally to win, which player wins?
Input
$N$ $A_1$ $\cdots$ $A_N$
- All inputs are integers.
- $1 \le N \le 200000$
- $1 \le A_1 \le \cdots \le A_N \le 10^9$
Output
Print First if the first player wins, and Second if the second player wins.
Sample
Sample 1
Input
2 1 2
Output
First
If the first player chooses pile $2$ and takes $1$ stone, the second player has no choice but to take a stone from pile $1$, so the first player wins.
Sample 2
Input
3 1 1 2
Output
Second
The first player can initially take $1$ stone from pile $1$ or $1$ stone from pile $3$.
If $1$ stone is taken from pile $1$, the second player takes $1$ stone from pile $3$, and the second player eventually wins.
If $1$ stone is taken from pile $3$, the second player then takes $1$ stone from pile $1$, and the second player eventually wins as well.
Therefore, whatever move the first player makes, the second player wins by acting appropriately.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。