← 返回题目列表

AtCoder · arc148_d

D. mod M 游戏

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

分数: 700 点

问题陈述

有 2N 整数 A_1, A_2, ..., A_{2N} ,还有一个整数 M 至少 2.
Alice 和 Bob 将玩一个游戏。 他们将交替执行以下操作,Alice 先进行,直到黑板上没有数字。

  • 选择一个数字并将其从黑板上删除。

游戏结束时,如果Alice删除的数字之和取模 M 等于 Bob 删除的数字之和取模 M,鲍勃获胜;否则,爱丽丝获胜。
如果双方都发挥最佳,哪位玩家会获胜?

约束

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • 0 \leq A_i \leq M - 1
  • 输入中的所有值都是整数。

输入

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

N M
A_1 A_2 \dots A_{2N}

输出

如果 Alice 获胜,则打印 Alice;如果鲍勃获胜,则打印 Bob.


示例输入 1

2 9
1 4 8 5

示例输出 1

Alice

游戏可按如下方式进行。

  • 爱丽丝删除 1.
  • 鲍勃删除 4.
  • 爱丽丝删除 5.
  • 鲍勃删除 8.

在本例中,Alice 删除的数字之和取模 M is (1 + 5) \bmod 9 = 6,以及 Bob 删除的数字之和取模 M is (4 + 8) \bmod 9 = 3。自从 6 \neq 3,爱丽丝获胜。


示例输入 2

3 998244353
1 2 3 1 2 3

示例输出 2

Bob