問題一覧 > 通常問題

No.715 集合と二人ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : ats5515ats5515 / テスター : tubo28tubo28
4 ProblemId : 1890 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-07-13 23:00:43

問題文

自然数の集合$S$について、初期状態におけるSの要素数$N$と$S$の要素$A_i$($1≤i≤N$)が与えられる。$S$を使った以下の二人ゲームを考える。
・二人のプレイヤーは交互に手番を持つ。
・手番を持つプレイヤーは、$S$から要素を一つ自由に選ぶ。選ばれた要素との差の絶対値が1以下の自然数をすべて$S$から削除する。
・先に行動できなくなったプレイヤー(すなわち、$S$が空になったときに手番がまわってきたプレイヤー)の負けとする。
先手必勝か後手必勝かを答えよ。

入力

N
A1 A2 ... AN

$1≤N≤5×10^5$
$1≤A_i≤10^9$($1≤i≤N$)
1行目には、初期状態における$S$の要素の個数$N$が与えられる。
2行目には、$S$の要素$A_i$($1≤i≤N$)がスペース区切りで与えられる。
$1≤i,j≤N$に対し、$i≠j$ならば$A_i≠A_j$であることが保証される。

出力

先手必勝ならば"First"、後手必勝ならば"Second"を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
1 2 3
出力
First

先手が2を選べば、Sは空になり後手の負けとなります。

サンプル2
入力
4
3 4 5 6
出力
Second

先手がどの数字を選んでも、後手が残った数字のどれかを選べばSは空となり、後手の勝ちです。

サンプル3
入力
8
1 2 4 5 7 8 10 11
出力
Second

サンプル4
入力
18
19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1
出力
Second

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。