Alice and Bob
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Alice and Bob like playing games.
There are $m$ numbers written on the blackboard, all of which are integers between $0$ and $n$.
The rules of the game are as follows:
If there are still numbers on the blackboard, and there are no numbers with value $0$ on the blackboard, Alice can divide the remaining numbers on the blackboard into two sets.
Bob chooses one of the sets and erases all numbers in that set. Then subtract all remaining numbers by one.
At any time, if there is a number with a value of $0$ on the blackboard, Alice wins; otherwise, if all the numbers on the blackboard are erased, Bob wins.
Please determine who will win the game if both Alice and Bob play the game optimally.
There are $m$ numbers written on the blackboard, all of which are integers between $0$ and $n$.
The rules of the game are as follows:
If there are still numbers on the blackboard, and there are no numbers with value $0$ on the blackboard, Alice can divide the remaining numbers on the blackboard into two sets.
Bob chooses one of the sets and erases all numbers in that set. Then subtract all remaining numbers by one.
At any time, if there is a number with a value of $0$ on the blackboard, Alice wins; otherwise, if all the numbers on the blackboard are erased, Bob wins.
Please determine who will win the game if both Alice and Bob play the game optimally.
Input
The first line contains an integer $T(T \le 2000)$ —the number of test cases.
The first line of each test case contains a single integers $n(1 \le \sum n \le 10^{6})$ .
The second line of each test case contains $n+1$ integers $a_0,a_1,a_2...a_n(0 \le a_i \le 10^{6} , \sum{a_i}=m)$ — there are $a_i$ numbers with value $i$ on the blackboard .
The first line of each test case contains a single integers $n(1 \le \sum n \le 10^{6})$ .
The second line of each test case contains $n+1$ integers $a_0,a_1,a_2...a_n(0 \le a_i \le 10^{6} , \sum{a_i}=m)$ — there are $a_i$ numbers with value $i$ on the blackboard .
Output
For each test case, print "Alice" if Alice will win the game, otherwise print "Bob".
Sample Input
2 1 0 1 1 0 2
Sample Output
Bob Alice
Source
2022“杭电杯”中国大学生算法设计超级联赛(1)