No.2044 Infinite Nim
タグ : / 解いたユーザー数 126
作問者 : 箱星 / テスター : hitonanode platinum
問題文
$N$ 個の石の山があり、$i$ 番目の山には石が $A_i$ 個あります。ただし石の数は無限になり得ます。$A_i=−1$ のとき、$i$ 番目の山には石が無限にあることを表します。
先手太郎君と後手次郎君はゲームを行います。先手太郎君から始めて、以下の操作を交互に行います。
-
$1$ 個以上石が存在する山を $1$ つ選び、$1$ 個以上石を取り除き、選んだ山にある石の数が有限個になるようにする。
より正確には、石が $x$ 個ある山を選んだとき、$x$ が有限ならば $y\lt x$ をみたす非負整数 $y$ を $1$ つ選び、この山の石の個数を $y$ にする。$x$ が無限ならば非負整数 $y$ を $1$ つ選び、この山の石の個数を $y$ にする。
先に手が打てなくなった人の負けです。$2$ 人が最適に行動したときに勝つのはどちらかを判定してください。
制約
- $1\le N\le 10^5$
- $1\le A_i\le 10^9$ または $A_i=-1$
- 入力はすべて整数
入力
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
出力
先手太郎君が勝つときは First
、後手次郎君が勝つときは Second
と出力してください。
サンプル
サンプル1
入力
4 1 3 5 7
出力
Second
石の数は有限個です。
サンプル2
入力
2 1 -1
出力
First
先手太郎君は石が無限個ある $2$ 番目の山から石を取り除き、この山の石を $1$ 個にすればよいです。
サンプル3
入力
8 123 -1 456 -1 789 -1 -1 -1
出力
First
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。