問題一覧 > 通常問題

No.1852 Divide or Reduce

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : 蜜蜂 / テスター : Mitarushi
5 ProblemId : 6767 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-26 00:08:52

問題文

N 個の山が並んでおり、 i 番目の山には Ai 個の石があります。
先手太郎君と後手次郎君が対戦ゲームをします。 先手太郎君と後手次郎君の手番が交互に訪れます。先手太郎君が先手です。 それぞれのプレイヤーは、手番において以下の 2 つの手 X,Y のうちどちらか 1 つを選んで打つ必要があります。

  • X : 石が 2 個以上ある山が 1 つ以上あるときのみ行える。 2 個以上の石がある山を 1 つ選ぶ。その山の石の個数を C として、 A+B=C を満たす正整数 A,B を宣言する。選んだ山の石を全て取り除き、 A 個の石、 B 個の石がある山を 1 つずつ作る。
  • Y : 石がどの山にも 2 個以上あるときのみ行える。全ての山から石を 1 つずつ取り除く。
先に手が打てなくなった人の負けです。 2 人が最適に行動したときに勝つのはどちらかを判定してください。

T 個のテストケースが与えられるので、その全てに答えてください。

入力

入力の 1 行目は以下の通りです。
T
そして、 T 個のテストケースが続きます。これらはそれぞれ以下の形式で与えられます。
N
A1  A2  AN

  • 1T2×105
  • 1N2×105
  • 1Ai109 ( 1iN )
  • 1 つの入力ファイルにおいて N の総和は 5×105 を超えない。
  • 入力は全て整数

出力

先手太郎君が勝つ場合、 First と出力してください。後手次郎君が勝つ場合、 Second と出力して改行してください。
これを T 個のテストケース全てについて行ってください。

サンプル

サンプル1
入力
3
2
3 4
1
1
7
20 22 2 12 2 13 77
出力
First
Second
First

  • 1 つめのテストケースについて、先手太郎君が勝利します。以下はそのような 2 人の行動の例です。
    • 先手太郎君が Y を行います。操作後、山は 2 個あり石の個数はそれぞれ 2,3 個です。
    • 後手次郎君が Y を行います。操作後、山は 2 個あり石の個数はそれぞれ 1,2 個です。
    • 先手太郎君が X を行います。 2 個石がある山を選び A=1,B=1 とします。操作後、山は 3 個あり石の個数はそれぞれ 1,1,1 個です。
    • 後手次郎君は手を打つことができないので負けとなります。よって先手太郎君の勝利です。
  • なお、これが最適な操作を行った場合の結果とは限りません。

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