← 返回题目列表

Codeforces · 2183/A

A. 二进制数组游戏

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

Alice 和 Bob 正在数组 $$$a$$$ 上玩游戏,数组 $$$a$$$ 大小为 $$$n$$$,仅包含数字 0 和 1。爱丽丝先行动,每个玩家轮流行动。

在玩家的回合中,他或她选择两个整数 $$$l$$$ 和 $$$r$$$,使得 $$$1 \leq l \color{red}{ \lt } r \leq |a|$$$ (这里,$$$|a|$$$ 表示 $$$a$$$ 的当前长度)。然后,子数组 $$$[a_l,a_{l+1},\ldots,a_r]$$$ 被替换为单个数字 $$$1-\operatorname{min}(a_l,a_{l+1},\ldots,a_r)$$$。也就是说,如果子数组中的所有数字都是 $$$1$$$,则删除子数组 $$$[a_l,a_{l+1},\ldots,a_r]$$$,并在子数组原来的位置插入数字 $$$0$$$。否则,子数组 $$$[a_l,a_{l+1},\ldots,a_r]$$$ 被删除,数字 $$$1$$$ 被插入子数组所在的位置。

当数组中只剩下一个数字时(该玩家无法进行合法的移动),游戏结束。如果最终数字是 $$$0$$$,则爱丽丝获胜。否则,鲍勃获胜。请确定谁以最佳发挥赢得了这场比赛。

输入

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

每个测试用例的第一行包含一个正整数$$$n$$$ ($$$3 \le n \le 100$$$),表示数组$$$a$$$的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 1$$$)。

输出

对于每个测试用例,输出 爱丽丝 如果爱丽丝获胜,并且 鲍勃 否则。您可以在任何情况下输出每个字符。例如,答案 爱丽丝, 爱丽丝, 爱丽丝, 爱丽丝 都将被解释为相同。

示例

输入
复制

7
3
1 1 0
3
1 1 1
3
0 1 0
4
0 0 0 0
5
1 0 1 0 1
6
0 1 0 1 0 1
6
0 1 0 1 0 0

输出
复制

Alice
Alice
Bob
Bob
Alice
Alice
Bob

注意

在第一个测试用例中,Alice 可以通过选择 $$$l=2$$$ 和 $$$r=3$$$ 获胜。由于 $$$1-\operatorname{min}(a_2,a_3)=1$$$,子数组 $$$[1,0]$$$ 被替换为单个整数 $$$1$$$,$$$a$$$ 变为 $$$[1,1]$$$。此时,轮到鲍勃了,他唯一的举动就是选择 $$$l=1$$$ 和 $$$r=2$$$。由于 $$$1-\operatorname{min}(a_1,a_2)=0$$$,数组 $$$a$$$ 变为 $$$[0]$$$。游戏现在结束,爱丽丝获胜,因为最后一个数字是 $$$0$$$。

在第二个测试用例中,Alice 可以通过在第一步中选择 $$$l=1$$$ 和 $$$r=3$$$ 来获胜。该数组变为 $$$[0]$$$,游戏立即结束,Alice 获胜。