2018 China Collegiate Programming Contest - Guilin Site J. stone game

J. Stone Game

time limit per test

1 second

memory limit per test

256 megabytes

Alice and Bob are always playing game! The game today is about taking out stone from the stone piles in turn.

There are n piles of stones, and the i-th pile contains A[i] stones.

As the number of stones in each pile differs from its neighbor’s, they determine to take out exactly one stone from one of them in one turn without breaking that property. Alice goes first.

The player who cannot take stone will lose the game.

Now you have to determine the winner given n numbers representing the piles, if they both play optimally.

You should notice that even a pile of 0 stone is still regarded as a pile!

Input

The first line of input file contains an integer T $(1\le T\le 100)$, describing the number of test cases.

Then there are 2 \times T lines, with every two lines representing a test case.

The first line of each test case contains only one integer n $(1\le n\le 10^5)$ as described above.

The second line of that contains exactly n numbers, representing the number of stone(s) in a pile in order. All these numbers are ranging in $[0,10^9]$.

It is guaranteed that the sum of n in all cases does not exceed $10^6$.

Output

You should output exactly T lines.

For each test case, print Case d: (d represents the order of the test case) first, then print the name of winner, Alice or Bob.

Example

input

Copy

2
2
1 3
3
1 3 1

output

Copy

Case 1: Alice
Case 2: Bob

Note

Sample 1:

There is a possible stone-taking sequence: $(1,3)\to (1,2)\to (0,2)\to (0,1)$

Here is an invalid sequence: $(1,3)\to (1,2)\to (1,1)\to (0,1)$. Though it has the same result as the first sequence, it breaks that property “the number of stones in each pile differs from its neighbor’s”.

Game theory + A topological sort

First of all, find the law , Start with two piles of stones and try , When I found taking an odd number of stones ,Alice win , Take an even number of stones ,Bob win .

such as 3 1

In the end 1 0, Take it 3 A stone , Then it must be Alice win .

such as 4 1

The final situation is 1 0, take 4 A stone , Then it must be Bob win .

In fact, it has nothing to do with the total number and size of stones , Just judge the parity . After taking two stone piles , Just try 3 More than one .

such as 1 3 1

The last thing is 0 1 0, take 4 A stone , still Bob win

So we can see , As long as the final state is determined , Then judge the parity of the stones , You can get the answer .

such as 5 4 8 9 7 3 6

The final state is 1 0 1 2 1 0 1

So we can think of the original array as a DAG, A small number points to a large number , Then sort by Topology , One increment at a time , Get the final sequence .

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
typedef long long ll;
using namespace std;
#define N 100005
int t, cnt;
ll sum = 0;
int a[N], in[N], f[N];
vector<int> edge[N];
int main() {
    
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    while (n--) {
    
        // scanf("%d", &t);
        cin >> t;
        for (int i = 1; i <= t; i++) {
    
            // scanf("%d", &a[i]);
            cin >> a[i];
            sum += a[i];
        }
        a[0] = a[t + 1] = 1e9 + 1;
        for (int i = 2; i <= t; i++) {
    
            if (a[i] > a[i - 1]) {
      // a[i-1]->a[i]
                // cout << a[i] << ' ' << a[i - 1] << ' ';
                edge[i - 1].push_back(i);
                in[i]++;
            }
            if (a[i] < a[i - 1]) {
      // a[i]->a[i-1]
                // cout << a[i] << ' ' << a[i - 1] << ' ';
                edge[i].push_back(i - 1);
                in[i - 1]++;
            }
        }
        //---------------------------------------
        queue<int> Q;
        for (int i = 1; i <= t; i++) {
    
            if (in[i] == 0) {
    
                Q.push(i);
            }
        }
        while (!Q.empty()) {
    
            int top = Q.front();
            Q.pop();
            for (int i = 0; i < edge[top].size(); i++) {
    
                int now = edge[top][i];
                f[now] = max(f[now], f[top] + 1);
                if (--in[now] == 0) {
    
                    Q.push(now);
                }
            }
        }
        //-------------------------------
        for (int i = 1; i <= t; i++) {
    
            sum -= f[i];
        }
        cnt++;
        if (sum % 2 == 1) {
    
            // printf("Case %d: Alice\n", cnt);
            cout << "Case " << cnt << ": "
                 << "Alice" << '\n';
        } else {
    
            // printf("Case %d: Bob\n", cnt);
            cout << "Case " << cnt << ": "
                 << "Bob" << '\n';
        }
        for (int i = 1; i <= t; i++) {
    
            edge[i].clear();
            f[i] = 0;
            in[i] = 0;
        }
        sum = 0;
    }
}