問題一覧 > 通常問題

No.2619 Sorted Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 : startcpp / テスター : 👑 Kazun
1 ProblemId : 7739 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-21 21:44:39

問題文

1,2,,N1, 2, \cdots, N があり、山 ii には AiA_i 個の石があります。
最初、A1ANA_1 \le \cdots \le A_N を満たします。

22 人が石取りゲームをします。先手, 後手が交互に次の操作をおこないます。
・石が 11 個以上存在する山を 11 つ選び、選んだ山から 11 個以上の石を取る

ただし、山 ii にある石の数を aia_i とおくとき、0a1a2aN0 \le a_1 \le a_2 \le \cdots \le a_N が保たれる操作しかおこなうことができないとします。

例えば、石が 3,4,63, 4, 6 個ある状態のとき、

  • 11 を選び、1,2,31, 2, 3 個の石を取る
  • 22 を選び、11 個の石を取る
  • 33 を選び、1,21, 2 個の石を取る
のいずれかをおこなうことができます。

先に操作できなくなった方が負けで、もう片方のプレイヤが勝ちます。
両者自分の勝ちを目指して最善を尽くすとき、どちらのプレイヤが勝つでしょうか。

入力

NN
A1A_1 \cdots ANA_N
  • 入力は整数
  • 1N2000001 \le N \le 200000
  • 1A1AN1091 \le A_1 \le \cdots \le A_N \le 10^9

出力

先手勝ちになるならFirst、後手勝ちになるならSecondを出力してください。

サンプル

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

先手が山 22 を選んで石を 11 つ取ると、後手は山 11 から石を取るしかなくなるので、先手が勝ちます。

サンプル2
入力
3
1 1 2
出力
Second

先手は、最初に山 11 から 11 個、または山 33 から 11 個の石を取ることができます。
11 から 11 個取った場合、後手が山 33 から 11 個の石を取ると、最終的に後手が勝ちます。
33 から 11 個取った場合も、後手は次に山 11 から 11 個の石を取り、最終的に後手が勝ちます。
よって、先手がいかなる手を打っても、後手が適切に行動することで後手が勝ちます。

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