← 返回题目列表

AtCoder · arc219_d

D. 网格游戏

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

分数: 500 点

问题陈述

有一个 N \times N 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i,j)。细胞 (i,j) 最初包含 A_{i,j} 石头。

Alice 和 Bob 使用此网格玩以下游戏。

  • 从 Alice 开始,两名玩家轮流轮流。
  • 每回合,玩家选择一个单元格并至少移动 1 最多 K 石头从它一起到上方或左侧的相邻单元格。具体来说,按顺序执行以下步骤:
    1. 选择一个单元格 (i,j) 至少包含 1 石头。细胞 无法选择 (1,1) 。
    2. 让 c 是单元格中宝石的数量 (i,j),然后选择一个整数 x 满意 1 \le x \le \min(c,K).
    3. 选择任一单元格作为目标 (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 在第一行。