C - 茶碗と豆 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の大きな茶碗が横 1 列に並んでいます。左から i (0 ≦ i ≦ N-1) 番目の茶碗を茶碗 i と呼ぶことにします。茶碗 i (1 ≦ i ≦ N-1) には整数 C_i が書かれており、中には A_i 個の豆が入っています。茶碗 0 には整数は書かれておらず、豆も入っていません。ゲーム好きな兄妹がこれらの茶碗と豆を使って以下のようなゲームをしようとしています。

  • プレイヤーは自分のターンに、茶碗 0 以外の茶碗に入っている豆 1 つ選んで取り出す。
  • 茶碗 i から豆を取り出したときは、茶碗 i - C_i, 茶碗 i - C_i + 1, ..., 茶碗 i-1 のいずれかの茶碗に豆を入れなければならない。
  • 交互にターンを繰り返し、自分のターンに選べる豆がなくなったプレイヤーの負けとなる（もう一方のプレイヤーが勝ちとなる）。

2 人ともが勝ちを目指して最適な戦略をとったとき、先手と後手のどちらが勝つでしょうか？

入力

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

N
C_1 A_1
C_2 A_2
:
C_{N-1} A_{N-1}
  • 1 行目には、茶碗の個数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N-1 行には、茶碗の情報が与えられる。このうち i (1 ≦ i ≦ N-1) 行目には、2 つの整数 C_i (1 ≦ C_i ≦ i), A_i (0 ≦ A_i ≦ 10^9) が与えられる。これは、茶碗 i に書かれた整数が C_i であり、中に A_i 個の豆が入っていることを表す。ただし、いずれかの茶碗には豆が入っていること、すなわち A_i の合計が 0 でないことが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 100 かつ A_i ≦ 10 を満たすデータセット 1 に正解した場合は、80 点が与えられる。
  • N ≦ 100 を満たすデータセット 2 に正解した場合は、上記とは別に 20 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 4 点が与えられる。

出力

先手が勝つ場合は First を、後手が勝つ場合は Second を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3
1 0
1 1

出力例1

Second

ゲームは、例えば以下のように進行します。

  • 1 ターン目：先手が茶碗 2 の豆を選んで取り出し、茶碗 1 に豆を入れる
  • 2 ターン目：後手が茶碗 1 の豆を選んで取り出し、茶碗 0 に豆を入れる
  • 3 ターン目：豆を選ぶことができないため、先手の負けとなる

この例の場合、各プレイヤーの行動の選択肢はどのターンにも 1 つしかないため必ずこのような結果となります。

入力例2

7
1 1
2 0
1 0
2 0
4 1
3 0

出力例2

First

ゲームは、例えば以下のように進行します。

  • 1 ターン目：先手が茶碗 5 の豆を選んで取り出し、茶碗 4 に豆を入れる
  • 2 ターン目：後手が茶碗 4 の豆を選んで取り出し、茶碗 2 に豆を入れる
  • 3 ターン目：先手が茶碗 2 の豆を選んで取り出し、茶碗 1 に豆を入れる
  • 4 ターン目：後手が茶碗 1 の豆を 1 つ選んで取り出し、茶碗 0 に豆を入れる
  • 5 ターン目：先手が茶碗 1 の豆を選んで取り出し、茶碗 0 に豆を入れる
  • 6 ターン目：豆を選ぶことができないため、後手の負けとなる

その他の進行でも、後手がどのような行動をとっても先手が適切な行動をとることによって勝つことができます。

入力例3

7
1 1
2 0
1 9
2 10
4 3
3 5

出力例3

Second