AT_arc105_d [ARC105D] Let's Play Nim
题目描述
有 $N$ 个编号为 $1$ 到 $N$ 的袋子和 $N$ 个编号为 $1$ 到 $N$ 的盘子。袋子 $i$ 中有 $a_i$ 个硬币。所有盘子一开始都是空的。
先手太郎君和后手次郎君进行对战游戏。两人轮流行动,太郎君先手。每位玩家在自己的回合可以选择以下两种操作之一:
1. (当存在至少一个有硬币的袋子时):选择一个有硬币的袋子和一个盘子,将该袋子中的所有硬币全部移到所选盘子中(无论该盘子上是否已有硬币都可以)。
2. (当所有袋子都没有硬币时):选择一个有硬币的盘子,从中取走至少一个硬币。
无法进行操作的一方判负。请判断在两人都采取最优策略的情况下,谁会获胜。
有 $T$ 组测试数据,请分别给出每组的答案。
输入格式
输入按以下格式从标准输入给出。
> $T$
> $\mathrm{case}_1$
> $\vdots$
> $\mathrm{case}_T$
每组数据格式如下:
> $N$ $a_1$ $a_2$ $\cdots$ $a_N$
输出格式
输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的胜者。如果先手太郎君获胜,输出 `First`;如果后手次郎君获胜,输出 `Second`。
说明/提示
### 限制
- 所有输入均为整数。
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^5$
- $1 \leq a_i \leq 10^9$
- 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。
### 样例解释 1
- 在第 $1$ 个测试用例中,后手次郎君获胜。两人的操作示例如下:
- 先手太郎君只能选择袋子 $1$ 并将硬币移到盘子 $1$。
- 后手次郎君选择盘子 $1$ 并移除所有硬币,使得先手太郎君无法再进行操作而输掉比赛。
- 注意,当存在有硬币的袋子时,只能选择将袋子中的硬币移到盘子中;当所有袋子都没有硬币时,只能选择从盘子中移除硬币。
由 ChatGPT 4.1 翻译