A16855 | $Divisive Battle$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Alice 和 Bob 正在玩一个数组 $a$ 上的游戏，初始时 $a$ 包含 $n$ 个正整数，Alice 先手。 每次轮到某个玩家时，如果 $a$ 是非递减的 $^{\text{∗}}$，游戏立即结束。否则，该玩家可以从数组中选择一个元素 $x$，以及正整数 $y, z$，满足 $1 < y, z < x$ 且 $x = yz$，然后将数组中的 $x$ 替换为 $y$ 和 $z$（在 $x$ 的原位置，顺序任意）。如果没有这样的操作可执行，游戏结束。 一旦游戏结束，如果 $a$ 是非递减的，则 Bob 获胜；否则 Alice 获胜。请判断如果双方都采用最优策略，谁将获胜。 $^{\text{∗}}$ 若对于所有 $1 \leq i \leq m-1$ 都有 $a_i \leq a_{i+1}$，其中 $m$ 为 $a$ 的长度，则称 $a$ 是非递减的。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例组数。 每组数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。 每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）。 所有测试用例中 $n$ 之和不超过 $10^5$。

对于每个测试用例，输出一行。如果 Alice 获胜，输出 "Alice"；如果 Bob 获胜，输出 "Bob"。判题系统区分大小写。

输入 #1

4
10
10 9 8 7 6 5 4 3 2 1
3
1 8192 677
2
6 5
2
6 7

输出 #1

Alice
Bob
Alice
Bob

C++ 编辑器

输入

输出