← 返回题目列表

AtCoder · arc218_b

B. 全部减

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

分数: 400 点

问题陈述

有 N 非负整数 A_1,A_2,\dots,A_N 写在黑板上。

Alice 和 Bob 玩游戏。从Alice开始,他们交替执行以下操作,将黑板上写的整数个数减少到的玩家 0 获胜。

  • 让 m 是当前黑板上写的最小非负整数。
    • If m > 0,选择一个正整数 x 之间 1 和 m,包括在内。将黑板上写下的每个整数替换为其当前值减去 x.
    • If m = 0,擦除一个或多个 黑板上写着 0。

当两名玩家都以最佳方式获胜时确定谁获胜。

T 给出了测试用例;解决它们中的每一个。

约束

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 0 \le A_i \le 10^9
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \dots A_N

输出

输出 T 行。的 i- 第行应包含 Alice 如果爱丽丝赢了 \mathrm{case}_i,或 Bob 如果鲍勃获胜。


示例输入 1

5
1
2
3
1 1 1
4
1 2 3 4
7
3 1 4 1 5 9 2
3
218 503 2026

示例输出 1

Alice
Bob
Bob
Bob
Alice

对于第一个测试用例,一个可能的游戏进程如下: 黑板上写着

  • 最初, 黑板上写着 2 。
  • 爱丽丝选择 x = 1。现在 1 。
  • 鲍勃选择 x = 1。现在 0 。
  • Alice 选择并删除一个 0。现在黑板上什么也没有写。

当两名玩家都以最佳方式获胜时,爱丽丝获胜。

对于第二个测试用例,一种可能的游戏进程如下: 黑板上写着

  • 最初, 黑板上写着 1,1,1 。
  • 爱丽丝选择 x = 1。现在 0,0,0 。
  • Bob 选择并删除了一个 0。现在 0,0 。
  • Alice 选择并删除一个 0。现在 0 。
  • Bob 选择并删除了一个 0。现在黑板上什么也没有写。

当两名玩家都以最佳方式获胜时,鲍勃获胜。