← 返回题目列表

AtCoder · arc163_e

E. Chmin 异或游戏

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

分数: 900 点

问题陈述

Alice 和 Bob 正在玩一个使用长度的游戏-N 非负整数序列 A=(A_1,A_2,\dots,A_N).

从 Alice 开始,他们轮流执行以下操作。不能先行动的玩家就输了。

  • 选择一个非负整数 X 使得有一个整数 i 满意 A_i > A_i \oplus X.
  • 对于每个 1 \le i \le N,替换 A_i 与 \min(A_i,A_i \oplus X).

当两名玩家都发挥最佳状态时确定谁获胜。

在这里, \oplus 表示按位异或。

你被给予 T 测试用例。找出每个问题的答案。

约束

  • 1 \le T \le 100
  • 1 \le N \le 100
  • 0 \le A_i \le 10^9

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里, \mathrm{case}_i 是 i- 第一个测试用例。每个测试用例均按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印 T 行。

的 i第行 (1 \le i \le T) 应包含 问题陈述中指定的 Alice 如果爱丽丝获胜,并且 Bob 如果鲍勃在 i- 第一个测试用例。


样本输入 1

5
2
3 1
5
1 1 1 1 1
4
0 0 0 0
4
8 1 6 4
5
3 8 7 12 15

示例输出 1

Bob
Alice
Bob
Bob
Alice

在第一个测试用例中,一个可能的游戏进程可能如下。

  • 爱丽丝选择 X=3。这个选择是有效的,因为 3 > 3 \oplus 3(=0) 为 i=1.
  • A=(3,1) 变为 A=(0,1).
  • 鲍勃选择 X=1。这个选择是有效的,因为 1 > 1 \oplus 1(=0) 为 i=2.
  • A=(0,1) 变为 A=(0,0).
  • 由于 Alice 无法选择任何 X,游戏结束。

在这种情况下,鲍勃获胜。

在第二个测试用例中,一种可能的游戏进程可能如下。

  • 爱丽丝选择 X=1。这个选择是有效的,因为 1 > 1 \oplus 1(=0) 为 i=1.
  • A=(1,1,1,1,1) 变为 A=(0,0,0,0,0).
  • 由于鲍勃无法选择任何 X,游戏结束。

在这种情况下,爱丽丝获胜。