← 返回题目列表

AtCoder · arc087_c

E. 无前缀游戏

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

分数: 700 点

问题陈述

对于字符串 s 和 t,我们会说 s 和 t 是 无前缀 当两者都不是另一个的前缀时。

让 L 是正整数。一组字符串 S 是 好的弦乐套装 当满足以下条件时:

  • 中的每个字符串 S 的长度介于 1 和 L (含)并由字符组成 0 和 1.
  • 中的任何两个不同的字符串 S 没有前缀。

我们有一套很好的琴弦 S = \{ s_1, s_2, ..., s_N \}。爱丽丝和鲍勃将互相玩一场游戏。他们将从Alice开始交替执行以下操作:

  • 添加一个新字符串 S。添加后, S 仍然必须是一个好的字符串集。

第一个无法执行操作的玩家输掉游戏。当双方都发挥最佳状态时确定游戏的获胜者。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq L \leq 10^{18}
  • s_1, s_2, ..., s_N 都是不同的。
  • { s_1, s_2, ..., s_N } 是一个很好的字符串集。
  • |s_1| + |s_2| + ... + |s_N| \leq 10^5

输入

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

N L
s_1
s_2
:
s_N

输出

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


示例输入 1

2 2
00
01

示例输出 1

Alice

如果爱丽丝添加 1,Bob 将无法添加新字符串。


示例输入 2

2 2
00
11

示例输出 2

Bob

Alice 在第一回合可以添加两个字符串: 01 和 10。 万一她补充说 01,如果鲍勃添加 10,她将无法添加新字符串。 另外,如果她补充说 10,如果鲍勃添加 01,她将无法添加新字符串。


示例输入 3

3 3
0
10
110

示例输出 3

Alice

如果爱丽丝添加 111,Bob 将无法添加新字符串。


示例输入 4

2 1
0
1

示例输出 4

Bob

Alice 无法在第一回合添加新字符串。


示例输入 5

1 2
11

示例输出 5

Alice

示例输入 6

2 3
101
11

示例输出 6

Bob