QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100

#9481. Min Nim

统计

有 $N$ 堆石子,第 $i$ 堆初始时有 $A_i$ 个石子。Anna 和 Bob 使用这些石堆进行游戏。

游戏由 Anna 先手,两人轮流进行以下操作:

  1. 选择一个包含至少一个石子的石堆 $i$ ($1 \le i \le N$)。
  2. 从第 $i$ 堆中移除一个或多个石子,使得操作后,第 $i$ 堆剩余的石子数量必须等于所有石堆中剩余石子数量的最小值。更正式地说,操作后必须满足以下条件: $$A'_i = \min\{A'_1, A'_2, \dots, A'_N\}$$ 其中 $A'_j$ 表示操作后第 $j$ 堆剩余的石子数量(若第 $j$ 堆为空,则 $A'_j = 0$)。

无法进行操作的玩家输掉游戏,未输掉游戏的玩家获胜。确定双方均采取最优策略时谁会获胜。

共需回答 $T$ 组测试用例。

输入格式

输入通过标准输入给出,格式如下:

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例的格式如下:

$N$ $A_1 \ A_2 \ \dots \ A_N$

  • $1 \le T$
  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^9$ ($i = 1, 2, \dots, N$)
  • 所有测试用例中 $N$ 的总和不超过 $10^5$。
  • 所有输入值均为整数。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试用例的获胜者。如果 Anna 获胜,输出 “First”,否则输出 “Second”。

样例

输入 1

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

输出 1

First
Second

说明

在第一个测试用例中,第一回合 Anna 可以执行以下操作之一:

  • 从第一堆中移除两个或更多石子。
  • 从第二堆中移除一个或更多石子。
  • 从第三堆中移除三个或更多石子。

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.