No.1208 anti primenumber game
タグ : / 解いたユーザー数 97
作問者 :
simasima_71
/ テスター :
kaage
問題文
$N$ 個の石の山が一列に並んでいます。
左から $i$ 番目の石の山には $A_i$ 個の石があります。
先手と後手はルールに従って交互に石を取ります。
相手より得点が高いほうが勝ちです。
同点の場合は後手の勝ちです。
＜ルール＞
石がある山の中で最も左の山から$1$個以上の石をいくつでも同時に取ります。
ただし、石を取られた山に残った石の個数が素数になってはいけません。
石を $1$ 個取るごとに $1$ 点もらえます。
各山の最後の石を取ると $M$ 点引かれます。
点数は負の数にもなります。
互いに最善を尽くすときどちらが勝ちますか？
入力
$N\ M$ $A_1\ \dots\ A_N$
入力は全て整数
$1 \le N \le 200000=2 \times 10^5$
$0 \le M \le 1000000000000=10^{12}$
$1 \le A_i \le 1000000000000=10^{12}$
注:$A_i$が素数である可能性もある。
出力
先手が勝つならFirst、後手が勝つならSecondを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 2 6 3 2
出力
First
ゲームの流れの一例を挙げます。ここで挙げられている手が最善とは限りません。
先手は一番左の山から $2$ 個石を取り、$2$ 点を取り、山の石を $4$ 個にします。
後手は一番左の山から $4$ 個石を取り、$4$ 点を取り、山の石を $0$ 個にします。
後手が一番左の山の最後の石を取ったので、後手の点数が $2$ 点引かれます。
先手は左から二番目の山から $2$ 個石を取り、$2$ 点を取り、山の石を $1$ 個にします。$1$ は素数ではないので大丈夫です。
後手は左から二番目の山から $1$ 個石を取り、$1$ 点を取り、山の石を $0$ 個にします。
後手が左から二番目の山の最後の石を取ったので、後手の点数が $2$ 点引かれます。
先手は左から三番目の山から $2$ 個石を取り、$2$ 点を取り、山の石を $0$ 個にします。
先手が左から三番目の山の最後の石を取ったので、先手の点数が $2$ 点引かれます。
この場合は先手が $4$ 点、後手は $1$ 点 なので先手の勝ちです。
サンプル2
入力
1 1000000000000 1
出力
Second
先手は $1$ 個の石を取らざるを得ません。(かわいそう…)
$-999999999999$ 対 $0$ で後手の勝ちです。
サンプル3
入力
2 0 1 1
出力
Second
$M$ が $0$ の時もあります。
先手も後手も一個ずつ石を取り、
$1$ 対 $1$ で同じ点数なので後手の勝ちです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。