031 - VS AtCoder(★6) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 6

問題文

あなたは、人気番組「VS AtCoder」に「チーム競技プログラマー」として参加しました。

この番組の最終ゲーム「リムービングストーン」のルールは、次の通りです。

ルール1 N 個の山が横一列に並んでいる。左から i 番目の山には、白石が W_i 個、青石が B_i 個ある。

ルール2 先攻から交互に、以下の操作を行わなければならない。

  • 白石が 1 個以上または青石が 2 個以上ある石の山を 1 つ選び、次の操作のうちいずれか一方のみを行う。ただし、選んだ山にある白石と青石の個数をそれぞれ w, b とする。
    • [w \geq 1 のとき選択可能] 選んだ山に青石を w 個加え、白石を 1 個取り除く。
    • [b \geq 2 のとき選択可能] 1 以上 \lfloor \frac{b}{2} \rfloor 以下の整数 k を選び、選んだ山から青石を k 個取り除く。

ルール3 初めて操作を行えなくなった人が負けである。つまり、初めて「すべての山について、白石が 0 個かつ青石が 1 個以下」という状況で自分の番を迎えた人が負けである。

あなたはこの番組のレギュラーである E869120 と直接対決をします。ゲストの特権により、あなたは先攻か後攻かを選ぶことができます。そして、このゲームの勝敗が全体の勝敗に直結するため、あなたは絶対にこのゲームで勝つ必要があります。

両者が最善を尽くすとき、あなたが勝つためには先攻・後攻のどちらを選ぶべきでしょうか?

\lfloor x \rfloor について\lfloor x \rfloor とは、x を超えない最大の整数を表します。
例えば、\lfloor 2.5 \rfloor = 2\lfloor 3 \rfloor = 3\lfloor 9.999999 \rfloor = 9 となります。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq W_i, B_i \leq 50
  • (W_i, B_i) \neq (0,0)
  • 入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

N
W_1 W_2 \dots W_N
B_1 B_2 \dots B_N

出力

あなたが先攻を選ぶべきであるならば First 、後攻を選ぶべきであるならば Second と出力してください。


入力例 1

1
0
2

出力例 1

First

あなたが先攻を選んだ場合、最初の操作で唯一の山から青石を 1 個だけ取り除くことができます。 この操作をすると、山の状態が「青石 1 個だけ」になり、E869120 が負け、あなたは勝ちます。 よって、先攻を選ぶべきです。


入力例 2

2
10 10
10 10

出力例 2

Second

あなたが後攻を選んだ場合、毎回の自分の操作において、E869120 が直前に行った操作をもう一方の山に対して行うことによって、あなたは勝つことができます。よって、後攻を選ぶべきです。


入力例 3

1
1
1

出力例 3

Second

あなたは後攻を選ぶべきです。なぜなら、以下のようにしかゲームが進行し得ないからです。

  • E869120 が最初青石を 1 個加え、白石を 1 個取り除く
  • 山の状態が「青石 2 個だけ」になる。そのとき、あなたは青石を 1 個取り除く操作しかできない。
  • すると、山の状態が「青石 1 個だけ」になり、E869120 は操作を行えなくなる。

入力例 4

6
3 1 4 1 5 9
2 7 1 8 2 8

出力例 4

Second

入力例 5

6
1 2 3 4 5 6
1 2 3 4 5 6

出力例 5

First

Source Name

「競プロ典型90問」31日目