BNUOJ 13105 nim博弈

时间：2022-02-27 18:49:58

ncredible Chess

Time Limit: 2000ms
Memory Limit: 32768KB

This problem will be judged on LightOJ. Original ID: 1186
64-bit integer IO format: %lld      Java class name: Main

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 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, W0, W1, ..., Wn-1 giving the position of the white pieces. The next line will also contain n integers, B0, B1, ... Bn-1 giving the position of the black pieces. Wimeans the row position of the white piece of ith column. And Bi means the row position of the black piece of ith column. You can assume that (0 ≤ Wi < Bi < 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 Input

Sample Input

Output for Sample Input

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

Case 1: black wins

Case 2: white wins

Source

题意：n*n的棋盘 黑白棋子 只能左右移动 不能移动的输 白棋先手
题解：尼姆博弈  将同一行的黑白棋子的间隔位置数量当作 经典题目中每一堆石子的数量 直接求取异或和
 /******************************

 code by drizzle

 blog: www.cnblogs.com/hsd-/

 ^ ^    ^ ^

  O      O

 ******************************/

 #include<bits/stdc++.h>

 #include<map>

 #include<set>

 #include<cmath>

 #include<queue>

 #include<bitset>

 #include<math.h>

 #include<vector>

 #include<string>

 #include<stdio.h>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #pragma comment(linker, "/STACK:102400000,102400000")

 using namespace std;

 #define  A first

 #define B second

 const int mod=;

 const int MOD1=;

 const int MOD2=;

 const double EPS=0.00000001;

 typedef __int64 ll;

 const ll MOD=;

 const int INF=;

 const ll MAX=1ll<<;

 const double eps=1e-;

 const double inf=~0u>>;

 const double pi=acos(-1.0);

 typedef double db;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 int t;

 int a[];

 int b[];

 int n;

 int ans;

 int main()

 {

     scanf("%d",&t);

     for(int i=; i<=t; i++)

     {

         scanf("%d",&n);

         for(int j=; j<=n; j++)

             scanf("%d",&a[j]);

         for(int j=; j<=n; j++)

             scanf("%d",&b[j]);

         ans=;

         for(int j=; j<=n; j++)

         {

             if(a[j]>b[j])

             ans=ans^(a[j]-b[j]-);

             else

             ans=ans^(b[j]-a[j]-);

         }

         if(ans==)

             printf("Case %d: black wins\n",i);

         else

             printf("Case %d: white wins\n",i);

     }

     return ;

 }

相关文章