← 返回题目列表

Codeforces · 1382/B

B. 顺序 Nim

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

有 $$$n$$$ 堆石头,其中第 $$$i$$$ 堆有 $$$a_i$$$ 石头。两个人玩一个游戏,轮流移走石头。

在一次移动中,玩家可以从第一个非空堆(索引最小的堆,至少有一个石子)中移除正数的石子。第一个无法移动的玩家(因为所有牌堆都是空的)就输掉了游戏。如果双方都发挥最佳,则确定游戏的获胜者。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$) — 堆的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — $$$a_i$$$ 等于第 $$$i$$$ 堆中的石头数量。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,如果先走一步的玩家获胜,则输出“First”。否则,输出“Second”。

示例

输入 #1

7
3
2 5 4
8
1 1 1 1 1 1 1 1
6
1 2 3 4 5 6
6
1 1 2 1 2 2
1
1000000000
5
1 2 2 1 1
3
1 1 1

输出 #1

First
Second
Second
First
First
Second
First

注意

在第一个测试用例中,第一个玩家将赢得游戏。他的制胜策略是:

1. 第一个玩家应该从第一堆中取出石子。他将拿走 $$$1$$$ 石头。一堆石头的数量将为 $$$[1, 5, 4]$$$。
2. 第二个玩家应该从第一堆中取出石子。他将拿走 $$$1$$$ 石头,因为他不能拿走任何其他数量的石头。成堆的石子数量为 $$$[0, 5, 4]$$$。
3. 第一个玩家应该从第二堆中取出石子,因为第一堆是空的。他将拿走 $$$4$$$ 石头。一堆石头的数量将为 $$$[0, 1, 4]$$$。
4. 第二个玩家应该从第二堆中取出石子,因为第一堆是空的。他将拿走 $$$1$$$ 石头,因为他不能拿走任何其他数量的石头。一堆石头的数量将为 $$$[0, 0, 4]$$$。
5. 第一个玩家应该从第三堆中取出石子,因为第一堆和第二堆都是空的。他将拿走 $$$4$$$ 石头。一堆石头的数量将为 $$$[0, 0, 0]$$$。
6. 第二个玩家将输掉游戏,因为所有牌堆都为空。