AtCoder Regular Contest 038
翻译中…
Problem Statement
翻译中…
$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$ 人ともが勝ちを目指して最適な戦略をとったとき、先手と後手のどちらが勝つでしょうか?
翻译中…
Input
翻译中…
入力は以下の形式で標準入力から与えられる。
翻译中…
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$点が与えられる。
翻译中…
Output
翻译中…
先手が勝つ場合は First を、後手が勝つ場合は Second を $1$ 行に出力せよ。出力の末尾に改行を入れること。
翻译中…
样例
Input #1
3
1 0
1 1
Output #1
Second
ゲームは、例えば以下のように進行します。
- $1$ ターン目:先手が茶碗 $2$ の豆を選んで取り出し、茶碗 $1$ に豆を入れる
- $2$ ターン目:後手が茶碗 $1$ の豆を選んで取り出し、茶碗 $0$ に豆を入れる
- $3$ ターン目:豆を選ぶことができないため、先手の負けとなる
この例の場合、各プレイヤーの行動の選択肢はどのターンにも $1$ つしかないため必ずこのような結果となります。
Input #2
7
1 1
2 0
1 0
2 0
4 1
3 0
Output #2
First
ゲームは、例えば以下のように進行します。
- $1$ ターン目:先手が茶碗 $5$ の豆を選んで取り出し、茶碗 $4$ に豆を入れる
- $2$ ターン目:後手が茶碗 $4$ の豆を選んで取り出し、茶碗 $2$ に豆を入れる
- $3$ ターン目:先手が茶碗 $2$ の豆を選んで取り出し、茶碗 $1$ に豆を入れる
- $4$ ターン目:後手が茶碗 $1$ の豆を $1$ つ選んで取り出し、茶碗 $0$ に豆を入れる
- $5$ ターン目:先手が茶碗 $1$ の豆を選んで取り出し、茶碗 $0$ に豆を入れる
- $6$ ターン目:豆を選ぶことができないため、後手の負けとなる
その他の進行でも、後手がどのような行動をとっても先手が適切な行動をとることによって勝つことができます。
Input #3
7
1 1
2 0
1 9
2 10
4 3
3 5
Output #3
Second
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。