No.1852 Divide or Reduce
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 :
蜜蜂
/ テスター :
Mitarushi
タグ : / 解いたユーザー数 53
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文最終更新日: 2022-02-26 00:08:52
問題文
$N$ 個の山が並んでおり、 $i$ 番目の山には $A_i$ 個の石があります。
先手太郎君と後手次郎君が対戦ゲームをします。 先手太郎君と後手次郎君の手番が交互に訪れます。先手太郎君が先手です。 それぞれのプレイヤーは、手番において以下の $2$ つの手 $X,Y$ のうちどちらか $1$ つを選んで打つ必要があります。
- $X$ : 石が $2$ 個以上ある山が $1$ つ以上あるときのみ行える。 $2$ 個以上の石がある山を $1$ つ選ぶ。その山の石の個数を $C$ として、 $A+B=C$ を満たす正整数 $A,B$ を宣言する。選んだ山の石を全て取り除き、 $A$ 個の石、 $B$ 個の石がある山を $1$ つずつ作る。
- $Y$ : 石がどの山にも $2$ 個以上あるときのみ行える。全ての山から石を $1$ つずつ取り除く。
$T$ 個のテストケースが与えられるので、その全てに答えてください。
入力
入力の $1$ 行目は以下の通りです。$T$そして、 $T$ 個のテストケースが続きます。これらはそれぞれ以下の形式で与えられます。
$N$
$A_1\ \ A_2\ \ \cdots A_N$
- $1 \leq T \leq 2 \times 10^5$
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$ ( $1 \leq i \leq N$ )
- $1$ つの入力ファイルにおいて $N$ の総和は $5 \times 10^5$ を超えない。
- 入力は全て整数
出力
先手太郎君が勝つ場合、 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もしくは右上の雲マークをクリックしてアカウントを作成してください。