格子棋游戏

题目描述

格鲁吉亚和鲍勃决定一起玩一个自创的游戏。

他们在纸上绘制一排网格，将网格从左到右依次编号 1,2,3,......，并将 N 个西洋棋棋子放在不同的网格上。

游戏规则

格鲁吉亚和鲍勃依次移动西洋棋棋子。

移动规则：

1. 每次玩家选择一个棋子，并将其向左移动
2. 不能越过任何其他西洋棋棋子
3. 不能超过左边界（即不能移动到位置 ≤ 0）
4. 玩家可以自由选择棋子移动的步数，但必须至少移动一步
5. 一个网格最多可以包含一个棋子（即移动后不能与其他棋子重叠）

输赢条件： 无法移动任何棋子的玩家将输掉游戏。

策略假设： 假设格鲁吉亚和鲍勃在游戏中都能够采取最好的策略，每次都由格鲁吉亚先手。

输入格式

第一行包含一个整数 T，表示共有 T 组测试数据。

每组测试数据包含两行：

1. 第一行包含整数 N，表示棋子数目
2. 第二行包含 N 个不同正整数（均不超过 10000），第 i 个表示第 i 个棋子的初始位置

输出格式

对于每组测试数据：

• 如果格鲁吉亚将赢得比赛，则输出 Georgia will win
• 如果鲍勃将赢得比赛，则输出 Bob will win
• 注意：题目说"否则输出 Not sure"，但根据博弈论分析，这种公平组合游戏在双方都采取最优策略时，结果应该是确定的，不会出现"Not sure"的情况

每个结果占一行。

数据范围

• $1 \le T \le 20$
• $1 \le N \le 1000$

输入样例

2
3
1 2 3
8
1 5 6 7 9 12 14 17

输出样例

Bob will win
Georgia will win

样例解释

第一个测试用例：N=3，棋子位置 [1, 2, 3]

棋子位置：1, 2, 3（相邻摆放）

分析： 这是一个经典的阶梯博弈（Staircase Nim）问题。

关键转化： 将棋子两两配对，从右向左考虑。对于棋子位置 $a_1 < a_2 < ... < a_N$（按升序排序），计算相邻棋子间的距离：

• 距离1：$a_2 - a_1$
• 距离2：$a_3 - a_2$
• ...
• 距离$N-1$：$a_N - a_{N-1}$

将这些距离分为奇数组和偶数组：

• 奇数距离：距离1, 3, 5, ...（即第1个和第2个棋子间的距离，第3个和第4个棋子间的距离，...）
• 偶数距离：距离2, 4, 6, ...（即第2个和第3个棋子间的距离，第4个和第5个棋子间的距离，...）

定理： 这个游戏等价于对奇数距离进行Nim游戏。

计算： 棋子位置：1, 2, 3

• 距离1：2 - 1 = 1
• 距离2：3 - 2 = 1

奇数距离（距离1）：1 偶数距离（距离2）：1

只考虑奇数距离的Nim和：1

结论： Nim和 = 1 ≠ 0，所以先手必胜（格鲁吉亚胜）。

但是样例输出是 Bob will win，这说明需要更仔细的分析。

重新分析： 实际上，对于相邻棋子的情况，需要特殊考虑。当棋子连续相邻时，先手可能反而会输。

考虑具体局面：

• 棋子1在位置1（最左边，不能再向左移动）
• 棋子2在位置2（只能移动到位置1，但位置1已被占据）
• 棋子3在位置3（只能移动到位置2，但位置2已被占据）

实际上，没有任何棋子可以移动！所以先手立即输。

因此输出 Bob will win。

第二个测试用例：N=8，棋子位置 [1, 5, 6, 7, 9, 12, 14, 17]

排序后：1, 5, 6, 7, 9, 12, 14, 17

计算相邻距离：

1. 5-1 = 4
2. 6-5 = 1
3. 7-6 = 1
4. 9-7 = 2
5. 12-9 = 3
6. 14-12 = 2
7. 17-14 = 3

奇数距离（第1,3,5,7个距离）：4, 1, 3, 3 Nim和：4 ⊕ 1 ⊕ 3 ⊕ 3 = (4⊕1=5) ⊕ (3⊕3=0) = 5 ⊕ 0 = 5 ≠ 0

所以先手（格鲁吉亚）必胜，输出 Georgia will win。

博弈论分析

阶梯博弈定理

对于这个游戏：

1. 将棋子按位置升序排序：$a_1 < a_2 < ... < a_N$
2. 计算相邻棋子间的距离：$d_i = a_{i+1} - a_i - 1$（减1是因为相邻棋子间至少空1格才能移动）
3. 将这些距离编号为1到N-1
4. 游戏等价于对奇数编号的距离（$d_1, d_3, d_5, ...$）进行Nim游戏

Nim游戏规则

• 有多堆石子，每堆有若干石子
• 玩家轮流从任意一堆中取走至少一个石子
• 取走最后一个石子的玩家获胜
• 先手必胜当且仅当各堆石子数的异或和不为0

应用到本题

1. 计算所有奇数编号距离的异或和
2. 如果异或和 ≠ 0，则先手（格鲁吉亚）必胜
3. 如果异或和 = 0，则后手（鲍勃）必胜

算法步骤

对于每组测试数据：

1. 读取N和棋子位置数组
2. 对棋子位置进行升序排序
3. 计算相邻距离：$d_i = a_{i+1} - a_i - 1$（i从1到N-1）
4. 计算奇数索引距离的异或和：$xor\_sum = d_1 ⊕ d_3 ⊕ d_5 ⊕ ...$
5. 判断：
   • 如果 $xor\_sum ≠ 0$，输出 Georgia will win
   • 否则，输出 Bob will win

注意事项

1. 棋子位置是不同的正整数
2. 移动时不能越过其他棋子
3. 游戏等价于对奇数距离进行Nim游戏
4. 边界情况：当棋子都在最左边时（如位置1,2,3），所有距离为0，异或和为0，后手必胜

时空限制

• 时间限制：1秒
• 空间限制：64MB