No.715 Set and Two-Player Game
Problem Statement
For a set $S$ of natural numbers, you are given the number of elements $N$ of S in the initial state and the elements $A_i$($1≤i≤N$) of $S$. Consider the following two-player game using $S$.
・The two players take turns alternately.
・The player whose turn it is freely chooses one element from $S$. All natural numbers whose absolute difference from the chosen element is at most 1 are removed from $S$.
・The player who first becomes unable to move (that is, the player whose turn comes when $S$ is empty) loses.
Determine whether the first player or the second player has a winning strategy.
Input
N A1 A2 ... AN
$1≤N≤5×10^5$
$1≤A_i≤10^9$($1≤i≤N$)
The first line contains the number of elements $N$ of $S$ in the initial state.
The second line contains the elements $A_i$($1≤i≤N$) of $S$, separated by spaces.
For $1≤i,j≤N$, it is guaranteed that $A_i≠A_j$ if $i≠j$.
Output
Print "First" if the first player has a winning strategy, or "Second" if the second player has a winning strategy.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
First
If the first player chooses 2, S becomes empty and the second player loses.
Sample 2
Input
4 3 4 5 6
Output
Second
Whichever number the first player chooses, S becomes empty when the second player chooses any of the remaining numbers, and the second player wins.
Sample 3
Input
8 1 2 4 5 7 8 10 11
Output
Second
Sample 4
Input
18 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Output
Second
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ats5515
tubo28