← 返回题目列表

AtCoder · abc206_f

F. 间歇游戏 2

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

分数: 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 获胜。

这些举动可能不是他们的最佳选择,但我们可以证明,如果双方都发挥最佳,鲍勃将获胜。

如第二个测试用例所示,测试用例内可以多次出现相同的间隔。