問題一覧 > 通常問題

No.2044 Infinite Nim

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

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。