CFCF2181F.Fragmented Nim

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

经典的 Nim 游戏规则如下:有 nn 堆石子,第 ii 堆初始有 aia_i 个石子。Alice 和 Bob 依次轮流操作,Alice 先手。每位玩家在自己的回合选择任意一堆非空的石子,并从中移除任意正整数个石子。取走最后一颗石子的玩家获胜。

在玩了很多次 Nim 之后,Alice 和 Bob 决定略微修改游戏规则。在这种变体中,轮到谁操作时,其对手选择一堆非空的石子,而当前玩家仍然可以决定从该堆中取走多少颗石子。

Alice 依旧先手。在 Alice 的回合,Bob 选择任意一堆非空的石子,然后 Alice 从中移除任意正整数个石子。类似地,在 Bob 的回合,Alice 选择一堆非空的石子,然后 Bob 从中移除任意正整数个石子。

对于给定的石子堆配置,如果双方都采用最优策略,请判断谁会获胜。

输入格式

每个测试点包含多组测试数据。第一行包含测试用例的数量 tt1t1041 \le t \le 10^4)。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 nn,表示石子的堆数(1n21051 \le n \le 2 \cdot 10^5)。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n,表示每堆的石子数量(1ai1091 \le a_i \le 10^9)。

保证所有测试用例中 nn 的总和不超过 21052 \cdot 10^5

输出格式

对于每组测试用例,如果双方都采取最优策略,请输出赢家的名字:“Alice” 或 “Bob”。

输入输出样例

  • 输入#1

    3
    3
    1 2 3
    1
    1
    5
    10 3 4 7 4

    输出#1

    Bob
    Alice
    Alice

说明/提示

在第一个测试用例中,游戏可能会如下进行:

  • Bob 选择第一堆。Alice 从中取走 11 颗石子。
  • Alice 选择第三堆。Bob 从中取走 22 颗石子。
  • Bob 选择第三堆。Alice 从中取走 11 颗石子。
  • Alice 选择第二堆。Bob 从中取走 22 颗石子并获胜。

在第二个测试用例中,Bob 只能选择唯一的一堆,Alice 取走这唯一的一颗石子获胜。

首页