← 返回题目列表

Codeforces · 1747/C

C. 交换游戏

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

Alice 和 Bob 正在一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 上玩游戏。爱丽丝和鲍勃交替移动,爱丽丝先走。

在他/她的回合中,玩家做出以下动作:

- 如果$$$a_1 = 0$$$,则玩家输掉游戏,否则:
- 玩家用 $$$2\le i \le n$$$ 选择一些 $$$i$$$。然后玩家将 $$$a_1$$$ 的值减少 $$$1$$$ 并将 $$$a_1$$$ 与 $$$a_i$$$ 交换。

如果双方都发挥最佳,则确定游戏的获胜者。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2 \ldots a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 Alice 将赢得游戏,则输出“Alice”。否则,输出“Bob”。

您可以在任何情况下输出每个字母。例如,“alIcE”、“Alice”、“alice”都将被视为相同。

示例

输入 #1

3
2
1 1
2
2 1
3
5 4 4

输出 #1

Bob
Alice
Alice

注意

在第一个测试用例中,Alice 只能选择 $$$i = 2$$$,使数组等于 $$$[1, 0]$$$。然后 Bob 也会选择 $$$i = 2$$$ 并使数组等于 $$$[0, 0]$$$。由于 $$$a_1 = 0$$$,爱丽丝输了。

在第二个测试用例中,玩家再次只能选择$$$i = 2$$$。那么数组将发生如下变化: $$$[2, 1] \to [1, 1] \to [1, 0] \to [0, 0]$$$,Bob 输了。

在第三个测试用例中,我们可以证明 Alice 有一个获胜策略。