分数: 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