← 返回题目列表

Codeforces · 1991/H

H. Prime 分割游戏

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

Alice 和 Bob 正在玩 $$$n$$$ 堆石子的游戏,其中第 $$$i$$$ 堆有 $$$a_i$$$ 石子。玩家轮流行动,爱丽丝先行动。

在每一步中,玩家都会执行以下三步过程:

1. 选择一个整数 $$$k$$$ ($$$1 \leq k \leq \frac n 2$$$)。请注意,对于不同的移动,$$$k$$$ 的值可能不同。
2. 移走 $$$k$$$ 堆石头。
3. 选择另外 $$$k$$$ 堆石头,并将每堆石头分成两堆。每堆新石子的数量必须是质数。

无法采取行动的玩家失败。

如果两名玩家都发挥最佳,确定谁会获胜。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 石子堆的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 堆中石子的数量。

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

输出

对于每个测试用例,如果 Alice 获胜,则输出“Alice”(不带引号),否则输出“Bob”(不带引号)。

您可以以任何大小写(大写或小写)输出每个字母。例如,字符串“alIcE”、“Alice”和“alice”都将被视为相同。

示例

输入 #1

4
2
2 1
3
3 5 7
4
4 6 8 10
5
8 8 8 8 8

输出 #1

Bob
Alice
Alice
Bob

注意

在第一个测试用例中,有 $$$2$$$ 堆石头,分别有 $$$2$$$ 和 $$$1$$$ 石头。由于 $$$1$$$ 和 $$$2$$$ 都不能分割成两个素数,所以 Alice 无法移动,所以 Bob 获胜。

在第二个测试用例中,有 $$$3$$$ 堆石头,分别有 $$$3$$$、$$$5$$$ 和 $$$7$$$ 石头。 Alice可以选择$$$k = 1$$$,移走$$$7$$$石头堆,然后将$$$5$$$石头堆分成两堆素数石头,$$$2$$$和$$$3$$$。然后,这堆石头由 $$$3$$$ 石头堆组成,分别是 $$$3$$$、$$$2$$$ 和 $$$3$$$ 石头,让鲍勃没有有效的移动,所以爱丽丝获胜。

在第三个测试用例中,有 $$$4$$$ 堆石头,分别有 $$$4$$$、$$$6$$$、$$$8$$$ 和 $$$10$$$ 石头。 Alice 可以选择 $$$k = 2$$$,移除两堆 $$$8$$$ 和 $$$10$$$ 石头。她将 $$$4$$$ 石头堆分成两堆素数石头 $$$2$$$ 和 $$$2$$$,并将 $$$6$$$ 石头堆分成 $$$3$$$ 和 $$$3$$$ 石头两堆。然后,鲍勃没有有效的动作,所以爱丽丝获胜。

在第四个测试用例中,有 $$$5$$$ 堆石头,每堆石头包含 $$$8$$$ 石头。可以证明,如果两个玩家都发挥最佳,鲍勃就会获胜。