← 返回题目列表

AtCoder · arc038_c

C. 碗和豆子

中文机器翻译题面 查看原题

問題文

N 大碗在旁边 1 排队。从左边开始 i (0 ≦ i ≦ N-1) 第碗 我们称之为 i 。茶碗 i (1 ≦ i ≦ N-1) 是一个整数 里面写着 C_i 。 包含 A_i 豆子。茶碗 0 不包含任何整数或 bean。一对热爱游戏的兄妹正在尝试用这些碗和豆子玩以下游戏。

  • 轮到玩家时, 除 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 Bean。然而,其中一个碗必须盛有豆子,即 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