分数: 500 点
问题陈述
有一个 N \times N 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i,j)。细胞 (i,j) 最初包含 A_{i,j} 石头。
Alice 和 Bob 使用此网格玩以下游戏。
- 从 Alice 开始,两名玩家轮流轮流。
- 每回合,玩家选择一个单元格并至少移动 1 最多 K 石头从它一起到上方或左侧的相邻单元格。具体来说,按顺序执行以下步骤:
- 选择一个单元格 (i,j) 至少包含 1 石头。细胞 无法选择 (1,1) 。
- 让 c 是单元格中宝石的数量 (i,j),然后选择一个整数 x 满意 1 \le x \le \min(c,K).
- 选择任一单元格作为目标 (i-1,j) (如果存在)或单元格 (i,j-1) (如果存在),然后删除 x 细胞内的结石 (i,j) 并将它们全部移至该单元格。
不能先轮到的玩家就输了。
确定当双方都发挥最佳状态时哪个玩家获胜。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T
- 2\le N\le 100
- 1\le K\le 10^9
- 0\le A_{i,j}\le 10^9
- 总和 N^2 所有测试用例最多 3\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出 Alice 如果 Alice 在双方都发挥最佳状态时获胜,并且 Bob 如果鲍勃获胜。
示例输入 1
3 2 2 0 1 3 2 3 1 1 1 1 1 1 1 1 1 1 4 4 3 8 5 3 4 2 0 6 0 9 10 4 1 9 7 10
示例输出 1
Alice Bob Alice
考虑第一个测试用例。
例如,游戏可能会按如下方式进行(请注意,玩家不一定处于最佳状态):
- 轮到爱丽丝了:选择单元格 (2,2) 并删除 2 石头。将移除的石头移至牢房 (1,2).
- 轮到鲍勃了:选择单元格 (1,2) 并删除 2 石头。将移除的石头移至牢房 (1,1).
- 轮到爱丽丝了:选择单元格 (2,1) 并删除 2 石头。将移除的石头移至牢房 (1,1).
- 轮到鲍勃了:选择单元格 (2,1) 并删除 1 石头。将移除的石头移至牢房 (1,1).
- 轮到爱丽丝了:选择单元格 (1,2) 并删除 1 石头。将移除的石头移至牢房 (1,1).
- 轮到鲍勃了:鲍勃不能轮流并输了。
通过最佳发挥,爱丽丝总能击败鲍勃。因此,输出 Alice 在第一行。