分数: 400 点
问题陈述
有 N 非负整数 A_1,A_2,\dots,A_N 写在黑板上。
Alice 和 Bob 玩游戏。从Alice开始,他们交替执行以下操作,将黑板上写的整数个数减少到的玩家 0 获胜。
- 让 m 是当前黑板上写的最小非负整数。
- If m > 0,选择一个正整数 x 之间 1 和 m,包括在内。将黑板上写下的每个整数替换为其当前值减去 x.
- If m = 0,擦除一个或多个 黑板上写着 0。
当两名玩家都以最佳方式获胜时确定谁获胜。
T 给出了测试用例;解决它们中的每一个。
约束
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N A_1 A_2 \dots A_N
输出
输出 T 行。的 i- 第行应包含 Alice 如果爱丽丝赢了 \mathrm{case}_i,或 Bob 如果鲍勃获胜。
示例输入 1
5 1 2 3 1 1 1 4 1 2 3 4 7 3 1 4 1 5 9 2 3 218 503 2026
示例输出 1
Alice Bob Bob Bob Alice
对于第一个测试用例,一个可能的游戏进程如下: 黑板上写着
- 最初, 黑板上写着 2 。
- 爱丽丝选择 x = 1。现在 1 。
- 鲍勃选择 x = 1。现在 0 。
- Alice 选择并删除一个 0。现在黑板上什么也没有写。
当两名玩家都以最佳方式获胜时,爱丽丝获胜。
对于第二个测试用例,一种可能的游戏进程如下: 黑板上写着
- 最初, 黑板上写着 1,1,1 。
- 爱丽丝选择 x = 1。现在 0,0,0 。
- Bob 选择并删除了一个 0。现在 0,0 。
- Alice 选择并删除一个 0。现在 0 。
- Bob 选择并删除了一个 0。现在黑板上什么也没有写。
当两名玩家都以最佳方式获胜时,鲍勃获胜。