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.
Fig 1: an example
There are two kinds of pieces, gray and white. Alice moves all gray pieces, and bob moves all 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.
At 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 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.
Fig 2: Moving the gray piece one cell to the right
Fig 3: 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.
Case 1: Alice
using namespace std;