問題一覧 > 通常問題

No.2044 Infinite Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : 箱星 / テスター : hitonanode platinum
9 ProblemId : 7207 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-09 22:12:20

問題文

NN 個の石の山があり、ii 番目の山には石が AiA_i 個あります。ただし石の数は無限になり得ますAi=1A_i=−1 のとき、ii 番目の山には石が無限にあることを表します。

先手太郎君と後手次郎君はゲームを行います。先手太郎君から始めて、以下の操作を交互に行います。

  • 11 個以上石が存在する山を 11 つ選び、11 個以上石を取り除き、選んだ山にある石の数が有限個になるようにする。

    より正確には、石が xx 個ある山を選んだとき、xx が有限ならば y<xy\lt x をみたす非負整数 yy11 つ選び、この山の石の個数を yy にする。xx が無限ならば非負整数 yy11 つ選び、この山の石の個数を yy にする。

先に手が打てなくなった人の負けです。22 人が最適に行動したときに勝つのはどちらかを判定してください。

制約

  • 1N1051\le N\le 10^5
  • 1Ai1091\le A_i\le 10^9 または Ai=1A_i=-1
  • 入力はすべて整数

入力

NN
A1A_1 A2A_2 \ldots ANA_N

出力

先手太郎君が勝つときは First、後手次郎君が勝つときは Second と出力してください。

サンプル

サンプル1
入力
4
1 3 5 7
出力
Second

石の数は有限個です。

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

先手太郎君は石が無限個ある 22 番目の山から石を取り除き、この山の石を 11 個にすればよいです。

サンプル3
入力
8
123 -1 456 -1 789 -1 -1 -1
出力
First

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