Incredible Chess

You are given an n x n chess board. Only pawn is used in the 'Incredible Chess' and they can move forward or backward. In each column there are two pawns, one white and one black. White pawns are placed in the lower part of the board and the black pawns are placed in the upper part of the board.

The game is played by two players. Initially a board configuration is given. One player uses white pieces while the other uses black. In each move, a player can move a pawn of his piece, which can go forward or backward any positive integer steps, but it cannot jump over any piece. White gives the first move.

The game ends when there is no move for a player and he/she will lose the game. Now you are given the initial configuration of the board. You have to write a program to determine who will be the winner.

Input

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

Each case starts with an integer n (3 ≤ n ≤ 100) denoting the dimension of the board. The next line will contain n integers, W₀, W₁, ..., W_n-1 giving the position of the white pieces. The next line will also contain n integers, B₀, B₁, ... B_n-1 giving the position of the black pieces. W_i means the row position of the white piece of i^th column. And B_i means the row position of the black piece of i^th column. You can assume that (0 ≤ W_i < B_i < n) for (0 ≤ i < n) and at least one move is remaining.

Output

For each case, print the case number and white wins or black wins depending on the result.

Sample

Sample Input	Sample Output
Click to copy 2 6 1 3 2 2 0 1 5 5 5 3 1 2 7 1 3 2 2 0 4 0 3 4 4 3 1 5 6	Click to copy Case 1: black wins Case 2: white wins

Total Submissions

Users Tried

Users Solved

LOJ 1186 - Incredible Chess

Summary

This game is played on an $n*n$ board. In each column there are two pawns, the higher one belongs to Alice, and the lower one belongs to Bob. Every pawns could go forward or backward any positive integer steps, but it couldn't jump over any piece in each move. The game ends when there is no move for a player and he/she will lose the game.

Solution

Hint 1

For each column, when a player goes backward $k$ steps, the other player only needs to go forward $k$ steps to keep the state unchanged. So we just need to consider the space between the two pawns in each column.

Hint 2

If we only need to consider the space between the two pawns in each column, we can think of the distance between the two pawns as stones, with each move taking some stone. Then this is just a Nim game.

So we only need to determine whether the $xor sum$ of the distances of all the columns is $0$.

Code

C++

#include <bits/stdc++.h>
using namespace std;

int t,n;
int w[105],b[105];

int main()
{
    scanf("%d",&t);
    for(int times=1;times<=t;times++)
    {
        int xorSum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            xorSum^=(b[i]-w[i]-1);
        }

        if(xorSum==0) printf("Case %d: black wins\n",times);
        else printf("Case %d: white wins\n",times);
    }
}

Tutorial source