[博弈]Swap Game Codeforces1747C

Alice and Bob are playing a game on an array aa of nn positive integers. Alice and Bob make alternating moves with Alice going first.

In his/her turn, the player makes the following move:

• If a1=0a1=0, the player loses the game, otherwise:
• Player chooses some ii with 2≤i≤n2≤i≤n. Then player decreases the value of a1a1 by 11 and swaps a1a1 with aiai.

Determine the winner of the game if both players play optimally.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤2⋅104)(1≤t≤2⋅104)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤105)(2≤n≤105)  — the length of the array aa.

The second line of each test case contains nn integers a1,a2…ana1,a2…an (1≤ai≤109)(1≤ai≤109)  — the elements of the array aa.

It is guaranteed that sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, if Alice will win the game, output "Alice". Otherwise, output "Bob".

You can output each letter in any case. For example, "alIcE", "Alice", "alice" will all be considered identical.

Example

input

3

2

1 1

2

2 1

3

5 4 4

output

Bob
Alice
Alice

题意： Alice和Bob轮流对数组a进行操作，Alice先手，每次操作先对a[1]减1，然后选择a[2]~a[n]中的一个位置i，将a[1]和a[i]进行交换。但轮到某人操作时a[1]等于0了，那他就输了，问最后谁获胜。

分析： 模拟一下游戏过程可以发现，谁先把a[1]减到0谁输，那么双方肯定会尽量挑选一个最小的数放在a[1]，这样对方才更有机会减到0。也就是说选数的最优策略是非常机械的，每次都选a[2]~a[n]中的最小值就行了。那么设x为a[2]~a[n]中的最小值，如果a[1]小于等于x，则Bob获胜，否则Alice获胜。

具体代码如下：

#include 
using namespace std;
 
int a[100005];
 
signed main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		int mn = *min_element(a+2, a+n+1);
		if(a[1] <= mn) puts("Bob");
		else puts("Alice");
	}
	return 0;
}