← 返回题目列表

AtCoder · arc208_a

A. 按位或游戏

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

分数: 500 点

问题陈述

有 N 成堆的石头,以及 i第一堆 (1\le i\le N) 有 A_i 石头。

Alice 和 Bob 将使用这些桩玩以下游戏:

  • 从 Alice 开始,两名玩家轮流轮流。
  • 在每一回合中,玩家选择一堆非空的石子,并从该堆中移走一颗或多颗石子。然而,玩家不能采取改变按位的动作 \mathrm{OR} 所有堆石子的数量。

无法先行动的玩家失败。

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

你被给予 T 测试用例;解决它们中的每一个。

什么是按位 \mathrm{OR}?

按位 \mathrm{OR} 非负整数的 A 和 B, A\ \mathrm{OR}\ B,定义如下:

  • 当 A\ \mathrm{OR}\ B 以二进制形式写入,其中的数字 2^k 地点(k \geq 0) 是 1 如果至少有一位数字 2^k 地点 A 和 B 写成二进制是 1,和 0 否则。
例如, 3\ \mathrm{OR}\ 5 = 7 (二进制: 011\ \mathrm{OR}\ 101 = 111).
一般来说,按位 \mathrm{OR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k),并且可以证明这与顺序无关 p_1, p_2, p_3, \dots p_k.

约束

  • 1\le T\le 10^5
  • 2\le N \le 2\times 10^5
  • 总和 N 所有测试用例最多 2\times 10^5.
  • 1\le A_i \le 10^9
  • 所有输入值均为整数。

输入

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

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

每个测试用例均按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

按顺序输出每个测试用例的答案,以换行符分隔。

对于每个测试用例,打印 Alice 如果当两个玩家都发挥最佳状态时爱丽丝获胜,并且 Bob 如果鲍勃获胜。


示例输入 1

4
3
3 4 6
3
7 7 7
3
9 3 5
10
1 9 1 3 7 9 10 9 7 3

示例输出 1

Alice
Bob
Bob
Alice

考虑第一个测试用例。

最初,按位 所有堆石子的数量 \mathrm{OR} 是 3\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=7.

Alice可以采取的动作如下:

  • 从第一堆中取出两块石头。
  • 从第二堆中取出一颗或多颗石头。
  • 从第三堆中取出一颗或多颗石头。

例如,如果爱丽丝从第一堆石头中取出一块石头,则按位 所有堆的石子数量的 \mathrm{OR} 变为 2\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=6。因此,爱丽丝不能采取从第一堆石头中取出一块石头的举动。

如果爱丽丝从第三堆中取出六颗石子,鲍勃在下一回合将无法进行任何移动。因此,当双方都发挥最佳状态时,Alice 获胜。