No.715 集合と二人ゲーム
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 :
ats5515
/ テスター :
tubo28
タグ : / 解いたユーザー数 43
作問者 :
ats5515
/ テスター :
tubo28
問題文最終更新日: 2018-07-13 23:00:43
問題文
自然数の集合$S$について、初期状態におけるSの要素数$N$と$S$の要素$A_i$($1≤i≤N$)が与えられる。$S$を使った以下の二人ゲームを考える。
・二人のプレイヤーは交互に手番を持つ。
・手番を持つプレイヤーは、$S$から要素を一つ自由に選ぶ。選ばれた要素との差の絶対値が１以下の自然数をすべて$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もしくは右上の雲マークをクリックしてアカウントを作成してください。