Left Right(LightOJ-1192)

题面

Two players, Alice and Bob are playing a strange game in a 1 x n board. The cells are numbered from 0 to n-1, where the left most cell is marked as cell 0. Each cell can contain at most one piece.

There are two kinds of pieces, gray and white. Alice moves all the gray pieces, and bob moves all the white ones. The pieces alternate, that is, leftmost piece is gray, next is white, next to that is gray, then it’s white again, and so on. There will always be equal number of black and gray pieces. Alice can only move pieces to the right. Bob can only move pieces to the left.

In each move, a player selects one piece and moves that piece, either to its left (Bob) or to its right (Alice), any number of cells (at least 1) but, it can neither jump over other pieces, nor it can move outside of the board. The players alternate their turns.

For example, if Alice decides to move the left most gray piece, these two moves are available to her.

	Illustration
Fig 1: Initial Position
Fig 2: Alice moving the gray piece one cell to the right
Fig 3: Alice moving the gray piece two cells to the right
Alice moves first. The game ends, when someone is unable to make any move, and loses the game. You can assume that, both of them play optimally (that is, if it is possible to apply a strategy that will ensure someone’s win, he/she will always use that strategy).

Now you are given a configuration of a board, you have to find the winner.

输入

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer k (1 ≤ k ≤ 100) denoting the number of gray pieces in the board. The next line contains 2k distinct integers (in ascending order) denoting the position of the pieces. The first integer denotes a gray piece, the second integer denotes a white piece, the next integer denotes a gray piece and so on. All the integers will lie in the range [0, 10^9].

Assume that n is sufficiently large to contain all the pieces. And at least one move is remaining.

输出

For each case, print the case number and Alice or Bob depending on the winner of the game.

样例输入

12
22
30 3 7 9
42
51 3 7 9

样例输出

1Case 1: Alice
2Case 2: Bob

提示

无

思路

Nim博弈，以间距为石子堆数做一个Nim博弈即可。

代码

 1using namespace std;
 2
 3int main()
 4{
 5    int T; scanf("%d", &T);
 6    for(int cs=1; cs<=T; cs++)
 7    {
 8        int n; scanf("%d", &n);
 9
10        int nim = 0;
11        for(int i=0; i<n; i++){
12            int a, b;
13            scanf("%d %d", &a, &b);
14            nim ^= b-a-1;
15        }
16
17        printf("Case %d: ", cs);
18        if(nim){
19            printf("Alice\n");
20        }else{
21            printf("Bob\n");
22        }
23
24    }
25    return 0;
26}