/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
長さ N の整数列 A があります。A の各要素は 0 または 1 です。
Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行います。
- A の要素から 1 であるものを 1 つ以上選び、それらを 0 にする。ただし、隣接する要素を同時に選ぶことはできない。
先に操作を行えなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 10^5
- 1 \le N \le 2\times 10^5
- A_i = 0 または A_i = 1
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各ケースは以下の形式で与えられる。
N A_1 A_2 \cdots A_N
出力
T 行出力せよ。i 行目には \text{case}_i について、Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。
入力例 1
3 5 1 0 1 0 1 2 1 1 14 1 1 1 0 1 1 1 1 0 1 1 1 1 1
出力例 1
Alice Bob Alice
1 つ目のテストケースについて、Alice が最初の操作で 1,3,5 番目の要素を選んで 0 にすることで、全ての要素を 0 にすることができます。
次に Bob は操作を行えないため、両者が最善を尽くしたとき Alice が勝利します。
2 つ目のテストケースについて、Alice は最初の操作でどちらか一方の要素しか選ぶことはできません。
Score : 600 points
Problem Statement
There is an integer sequence A of length N. Each element of A is 0 or 1.
Alice and Bob play a game. Starting with Alice, they alternately perform the following operation.
- Choose one or more elements of A that are 1, and set them to 0. Here, it is forbidden to choose adjacent elements simultaneously.
The player who is first unable to perform the operation loses.
Determine which player wins when both players play optimally.
You are given T test cases; solve each of them.
Constraints
- 1 \le T \le 10^5
- 1 \le N \le 2\times 10^5
- A_i = 0 or A_i = 1.
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each case is given in the following format:
N A_1 A_2 \cdots A_N
Output
Output T lines. The i-th line should contain Alice if Alice wins for \text{case}_i, and Bob if Bob wins.
Sample Input 1
3 5 1 0 1 0 1 2 1 1 14 1 1 1 0 1 1 1 1 0 1 1 1 1 1
Sample Output 1
Alice Bob Alice
For the first test case, Alice can set all elements to 0 by choosing the first, third, and fifth elements and setting them to 0 in her first operation.
Then, Bob cannot perform an operation, so Alice wins when both players play optimally.
For the second test case, Alice can only choose one of the two elements in her first operation.