分数: 600 点
问题陈述
解决以下问题 T 测试用例。
我们有 N 半开区间 [L_i,R_i) (1 \le i \le N)。使用它们,爱丽丝和鲍勃将玩以下游戏:
- Alice 和 Bob 交替执行以下操作,Alice 先进行。
- 来自 N 间隔,选择一个不与已选择的任何间隔相交的间隔。
无法进行操作的玩家失败,另一位玩家获胜。
如果两名玩家都以最佳方式获胜,哪位玩家会获胜?
什么是半开区间?
半开区间 [X,Y) 是由所有实数组成的区间 x 满意 X \leq x < Y.约束
- 输入中的所有值都是整数。
- 1 \le T \le 20
- 1 \le N \le 100
- 1 \le L_i < R_i \le 100
输入
输入由标准输入给出。第一行的格式如下:
T
然后, T 测试用例如下,每个测试用例的格式如下:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
打印 T 行。
的 i- 第行应包含 Alice 如果爱丽丝在比赛中获胜 i- 第一个测试用例,以及 Bob 如果鲍勃获胜。
示例输入 1
5 3 53 98 8 43 12 53 10 4 7 5 7 3 7 4 5 5 8 6 9 4 8 5 10 1 9 5 10 2 58 98 11 29 6 79 83 44 83 38 74 49 88 18 45 64 99 1 5 9
示例输出 1
Bob Alice Bob Alice Alice
此输入包含五个测试用例。
对于第一个测试用例,我们将在下面展示游戏的一个可能的进展。
- Alice 选择间隔 [12,53).
- Bob 选择间隔 [53,98)。请注意 [12,53) 和 [53,98) 不相交,因为它们是半开的。
- Alice 无法执行操作,Bob 获胜。
这些举动可能不是他们的最佳选择,但我们可以证明,如果双方都发挥最佳,鲍勃将获胜。
如第二个测试用例所示,测试用例内可以多次出现相同的间隔。