QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100 Hackable ✓

#12658. 杯子与豆子

Statistics

有 $N$ 个杯子,编号为 $0$ 到 $N-1$。对于每个 $i$ ($1 \le i \le N-1$),杯子 $i$ 中包含 $A_i$ 颗豆子,且该杯子被标记为一个整数 $C_i$。

两个人进行如下游戏:

  • 在每一轮中,玩家从除 $0$ 号杯子以外的任意一个杯子中选择一颗豆子。
  • 如果玩家选择的是 $i$ 号杯子中的豆子,他必须将其移动到 $i - C_i, \dots, i - 1$ 号杯子中的任意一个。
  • 玩家轮流进行操作。如果一名玩家无法选择豆子,则该玩家输掉比赛。

若双方均采取最优策略,谁会获胜?

输入格式

$N$ $C_1 \ A_1$ $C_2 \ A_2$ $\vdots$ $C_{N-1} \ A_{N-1}$

数据范围

  • $2 \le N \le 10^5$
  • $1 \le C_i \le i$
  • $0 \le A_i \le 10^9$
  • 至少有一个 $A_i$ 不为 $0$。
  • 输入中的所有值均为整数。

输出格式

输出获胜者的名字:“First” 或 “Second”。

样例

样例输入 1

3
1 0
1 1

样例输出 1

Second

样例输入 2

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

样例输出 2

First

样例输入 3

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

样例输出 3

Second

说明

样例 1 的说明:

  • 在第一轮中,先手玩家必须将一颗豆子从 $2$ 号杯子移动到 $1$ 号杯子。
  • 在第二轮中,后手玩家必须将一颗豆子从 $1$ 号杯子移动到 $0$ 号杯子。
  • 在第三轮中,先手玩家无法选择豆子,因此输掉比赛。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.