問題一覧 > 通常問題

No.2282 Boxed Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 : みここ / テスター : cureskol 箱星 👑 potato167
6 ProblemId : 9167 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-29 09:55:52

問題文

NN 個の箱があり、ii 番目の箱の中には AiA_i 個の石が入っています。はじめすべての箱はふたが閉まっています。

二人のプレイヤーがこれらの箱を使ってゲームをします。先手のプレイヤーから順に、二人は交互に以下のどちらかの操作を行います。

  • ふたが閉まっている箱を一つ選び、その箱のふたを開ける。
  • ふたが開いていて石が一つ以上入っている箱を一つ選び、箱に入っている石を一つ以上取り除く。

はじめに操作を行えなくなった方が負けで、そうでない方が勝ちです。

二人が最適に行動したとき、ゲームに勝つ方を求めてください。

入力

NN
A1 A2  ANA_1 \ A_2 \ \cdots \ A_N
  • 入力される値はすべて整数
  • 1N1051 \le N \le 10^5
  • 0Ai1090 \le A_i \le 10^9

出力

先手が勝つ場合 First を、後手が勝つ場合 Second を出力してください。

サンプル

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

ゲームの進行の一例を示します。

  1. 先手が 22 番目の箱を開ける。
  2. 後手が 11 番目の箱を開ける。
  3. 先手が 22 番目の箱から石を 11 個取り出す。
  4. 後手が 33 番目の箱を開ける。
  5. 先手が 33 番目の箱から石を 22 個取り出す。

その後、後手は操作を行うことができないため、先手の勝ちとなります。

サンプル2
入力
2
1 1
出力
Second
サンプル3
入力
8
2 0 2 3 0 2 1 0
出力
First

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