/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) を用いて Alice と Bob はゲームをします。
Alice から以下の操作を交互に行います。先に操作が出来なくなった方が負けです。
- A_i > A_i \oplus X を満たす整数 i が存在するような非負整数 X を選ぶ。
- 1 \le i \le N に対して A_i を \min(A_i,A_i \oplus X) で置き換える。
両者が勝つために最善な行動をしたとき、勝つのがどちらか判定してください。
ただしここで、\oplus はビットごとの排他的論理和を表します。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 100
- 1 \le N \le 100
- 0 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
ここで、\mathrm{case}_i とは i 個目のテストケースである。各テストケースは以下の形式で与えられる。
N A_1 A_2 \dots A_N
出力
T 行出力せよ。
i(1 \le i \le T) 行目には、i 個目のテストケースにおいて Alice が勝つならば Alice、Bob が勝つならば Bob を出力せよ。
入力例 1
5 2 3 1 5 1 1 1 1 1 4 0 0 0 0 4 8 1 6 4 5 3 8 7 12 15
出力例 1
Bob Alice Bob Bob Alice
1 個目のテストケースは、あり得るゲームの進行として以下のようなものが考えられます。
- Alice が X=3 を選ぶ。i=1 において 3 > 3 \oplus 3(=0) であるためこの選択は有効である。
- A=(3,1) から A=(0,1) となる。
- Bob が X=1 を選ぶ。i=2 において 1 > 1 \oplus 1(=0) であるためこの選択は有効である。
- A=(0,1) から A=(0,0) となる。
- Alice が選べる X が存在しないため、ゲームを終了する。
この場合 Bob が勝ちます。
2 個目のテストケースは、あり得るゲームの進行として以下のようなものが考えられます。
- Alice が X=1 を選ぶ。i=1 において 1 > 1 \oplus 1(=0) であるためこの選択は有効である。
- A=(1,1,1,1,1) から A=(0,0,0,0,0) となる。
- Bob が選べる X が存在しないため、ゲームを終了する。
この場合 Alice が勝ちます。
Score : 900 points
Problem Statement
Alice and Bob are playing a game using a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N).
Starting with Alice, they take turns performing the following operation. The player who cannot make a move first loses.
- Choose a non-negative integer X such that there is an integer i satisfying A_i > A_i \oplus X.
- For each 1 \le i \le N, replace A_i with \min(A_i,A_i \oplus X).
Determine who wins when both players play optimally.
Here, \oplus represents the bitwise XOR.
You are given T test cases. Find the answer for each of them.
Constraints
- 1 \le T \le 100
- 1 \le N \le 100
- 0 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Here, \mathrm{case}_i is the i-th test case. Each test case is given in the following format:
N A_1 A_2 \dots A_N
Output
Print T lines.
The i-th line (1 \le i \le T) should contain Alice if Alice wins, and Bob if Bob wins in the i-th test case.
Sample Input 1
5 2 3 1 5 1 1 1 1 1 4 0 0 0 0 4 8 1 6 4 5 3 8 7 12 15
Sample Output 1
Bob Alice Bob Bob Alice
In the first test case, one possible game progression could be as follows.
- Alice chooses X=3. This choice is valid because 3 > 3 \oplus 3(=0) for i=1.
- A=(3,1) becomes A=(0,1).
- Bob chooses X=1. This choice is valid because 1 > 1 \oplus 1(=0) for i=2.
- A=(0,1) becomes A=(0,0).
- Since Alice cannot choose any X, the game ends.
In this case, Bob wins.
In the second test case, one possible game progression could be as follows.
- Alice chooses X=1. This choice is valid because 1 > 1 \oplus 1(=0) for i=1.
- A=(1,1,1,1,1) becomes A=(0,0,0,0,0).
- Since Bob cannot choose any X, the game ends.
In this case, Alice wins.