AT_abc206_f [ABC206F] Interval Game 2

题目描述

请针对 $T$ 个测试用例，解决以下问题。

有 $N$ 个半开区间 $[L_i, R_i)$（$1 \le i \le N$），Alice 和 Bob 使用这些区间进行如下游戏：

• 游戏由 Alice 先手，双方轮流进行如下操作：
  • 从 $N$ 个区间中选择一个与已经被选中的所有区间都没有公共点的区间。

无法进行操作的一方判负，另一方获胜。 假设双方都采取最优策略，问最终谁会获胜？

半开区间的定义：半开区间 $[X, Y)$ 表示所有满足 $X \le x < Y$ 的实数 $x$ 组成的区间。

输入格式

输入从标准输入读入。输入的第 $1$ 行为：

$T$

接下来有 $T$ 个测试用例。每个测试用例的格式如下：

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出格式

请输出共 $T$ 行。 第 $i$ 行输出第 $i$ 个测试用例的结果，如果 Alice 获胜则输出 Alice，如果 Bob 获胜则输出 Bob。

输入输出样例 #1

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $1 \le T \le 20$
• $1 \le N \le 100$
• $1 \le L_i < R_i \le 100$

样例解释 1

本输入包含 $5$ 个测试用例。以第 $1$ 个测试用例为例，游戏可能如下进行：

• Alice 选择区间 $[12,53)$。
• Bob 选择区间 $[53,98)$。 由于游戏使用的是半开区间，$[12,53)$ 和 $[53,98)$ 没有公共点。
• Alice 无法再进行操作，判负。Bob 获胜。

上述步骤未必是双方的最优策略，但可以证明在双方都采取最优策略时，Bob 会获胜。 对于第 $2$ 个测试用例，可能会出现同一个区间被多次给出的情况。

由 ChatGPT 4.1 翻译