問題一覧 > 通常問題

No.2619 Sorted Nim

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

問題文

山 $1, 2, \cdots, N$ があり、山 $i$ には $A_i$ 個の石があります。
最初、$A_1 \le \cdots \le A_N$ を満たします。

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

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

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

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

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

入力

$N$
$A_1$ $\cdots$ $A_N$
  • 入力は整数
  • $1 \le N \le 200000$
  • $1 \le A_1 \le \cdots \le A_N \le 10^9$

出力

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

サンプル

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

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

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

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

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