F - Interval Game 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

T 個のテストケースについて、以下の問題を解いてください。

N 個の半開区間 [L_i,R_i) (1 \le i \le N) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。

  • Alice から始めて、以下の操作を交互に行う。
    • N 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を 1 つ選ぶ。

先に操作を行えなくなった方が負けで、もう片方のプレイヤーが勝ちます。
双方のプレイヤーが勝利に対して最善を尽くした場合、どちらが勝つことになりますか？

半開区間とは？半開区間 [X,Y) とは、 X 以上 Y 未満のすべての実数からなる区間です。

制約

  • 入力は全て整数
  • 1 \le T \le 20
  • 1 \le N \le 100
  • 1 \le L_i < R_i \le 100

入力

入力は標準入力から与えられる。入力の 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

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

この入力には、 5 つのテストケースが含まれます。

1 つ目のテストケースについて、例えば以下のようにゲームが進行します。

  • Alice が区間 [12,53) を選択する。
  • Bob が区間 [53,98) を選択する。 ゲームに用いる区間は半開区間なので、 [12,53),[53,98) は共有点を持たない。
  • Alice はこれ以上操作を行えず、負ける。 Bob はゲームに勝つ。

このテストケースについて、上記の手順が必ずしも両者にとって最善とは限りませんが、両者が最善を尽くした場合勝利するのは Bob であることが示せます。

2 つ目のテストケースのように、ひとつのテストケースに同じ区間が複数含まれる場合もあります。

Score : 600 points

Problem Statement

Solve the problem below for T test cases.

We have N half-open intervals [L_i,R_i) (1 \le i \le N). Using them, Alice and Bob will play the following game:

  • Alice and Bob alternately do the following operation, Alice going first.
    • From the N intervals, choose one that does not intersect with any of the intervals that are already chosen.

The player who gets unable to do the operation loses, and the other player wins.
Which player will win if both players play optimally to win?

What is a half-open interval?A half-open interval [X,Y) is an interval consisting of all real numbers x satisfying X \leq x < Y.

Constraints

  • All values in input are integers.
  • 1 \le T \le 20
  • 1 \le N \le 100
  • 1 \le L_i < R_i \le 100

Input

Input is given from Standard Input. The first line is in the following format:

T

Then, T test cases follow, each of which is in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print T lines.
The i-th line should contain Alice if Alice wins in the i-th test case, and Bob if Bob wins.

Sample Input 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

Sample Output 1

Bob
Alice
Bob
Alice
Alice

This input contains five test cases.

For the first test case, we will show one possible progression of the game below.

  • Alice chooses the interval [12,53).
  • Bob chooses the interval [53,98). Note that [12,53) and [53,98) do not intersect since they are half-open.
  • Alice is unable to do an operation, and Bob wins.

These moves may not be the best choices for them, but we can show that Bob will win if both play optimally.

As seen in the second test case, there can be multiple occurrences of the same interval within a test case.