← 返回题目列表

Codeforces · 1965/A

A. 一切尼姆

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

Alice 和 Bob 正在 $$$n$$$ 堆石头上玩游戏。在每个玩家的回合中,他们选择一个正整数 $$$k$$$,该整数最多为最小非空堆的大小,并立即从每个非空堆中移除 $$$k$$$ 石子。第一个无法移动的玩家(因为所有牌堆都是空的)就输了。

鉴于 Alice 先走,如果双方都发挥最佳,谁会赢得比赛?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 游戏中的桩数。

每个测试用例的下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 堆中石子的初始数量。

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

输出

对于每个测试用例,假设两个玩家都发挥最佳状态,打印一行包含获胜者姓名的行。如果 Alice 获胜,则打印“Alice”,否则打印“Bob”(不带引号)。

示例

输入 #1

7
5
3 3 3 3 3
2
1 7
7
1 3 9 7 4 2 100
3
1 2 3
6
2 1 3 4 2 4
8
5 7 2 9 6 3 3 2
1
1000000000

输出 #1

Alice
Bob
Alice
Alice
Bob
Alice
Alice

注意

在第一个测试用例中,Alice 可以通过在第一回合选择 $$$k=3$$$ 来获胜,这将立即清空所有堆。

在第二个测试用例中,Alice 必须在第一回合选择 $$$k=1$$$,因为有一堆大小 $$$1$$$,因此 Bob 可以通过选择 $$$k=6$$$ 在下一回合获胜。