No.2282 Boxed Nim
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : みここ / テスター : cureskol 箱星 👑 potato167
タグ : / 解いたユーザー数 149
作問者 : みここ / テスター : cureskol 箱星 👑 potato167
問題文最終更新日: 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
ゲームの進行の一例を示します。
- 先手が $2$ 番目の箱を開ける。
- 後手が $1$ 番目の箱を開ける。
- 先手が $2$ 番目の箱から石を $1$ 個取り出す。
- 後手が $3$ 番目の箱を開ける。
- 先手が $3$ 番目の箱から石を $2$ 個取り出す。
その後、後手は操作を行うことができないため、先手の勝ちとなります。
サンプル2
入力
2 1 1
出力
Second
サンプル3
入力
8 2 0 2 3 0 2 1 0
出力
First
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。