問題一覧 > 通常問題

No.2282 Boxed Nim

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

問題文

$N$ 個の箱があり、$i$ 番目の箱の中には $A_i$ 個の石が入っています。はじめすべての箱はふたが閉まっています。

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

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

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

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

入力

$N$
$A_1 \ A_2 \ \cdots \ A_N$
  • 入力される値はすべて整数
  • $1 \le N \le 10^5$
  • $0 \le A_i \le 10^9$

出力

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

サンプル

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

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

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

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

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

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