2014
02-17

# Game

After played many kinds of nim games, Xay and Amr decided to play something different. As the judge, I wrote several valid pairs of numbers on the blackboard. For every pair (x, y), it is valid only if -y ≤ x ≤ y and the greatest common divisor of x and y is 1. The typical legal move is to alter just one of these pairs. If we change (x, y) to (a, b):
1. (a, b) should be a valid pair.
2. 1 ≤ b < y if y != 1
3. 1 ≤ b ≤ y, -b < a < b if y = 1.

Furthermore, such a replacement will be legal for Xay only if a*y – b*x < 0, legal for Amr only if a*y – b*x > 0.For example, Xay can change (2, 5) to (1,3), (1,4), (-1,2), (0,1), (-1,1), etc. And Amr can similarly change (2, 5) to (1, 2), (2, 3), (3, 4), (1, 1), etc.

They will play on these pairs alternately. The last one who be able to move is the winner .We have already knew that both Amr and Xay are very clever and they will play this game perfectly. Now, my dear programmers, can you predict that who will be the winner?

The first line contains a single positive integer T. which is the number of test cases. Each test case starts with a line with a single positive integer n(1 ≤ n ≤ 100) and a string “Xay” or “Amr” means who moves first. Then n lines follows, each line contains a pair of integers x and y. (1 ≤ y ≤ 15 and �y ≤ x ≤ y)

The first line contains a single positive integer T. which is the number of test cases. Each test case starts with a line with a single positive integer n(1 ≤ n ≤ 100) and a string “Xay” or “Amr” means who moves first. Then n lines follows, each line contains a pair of integers x and y. (1 ≤ y ≤ 15 and �y ≤ x ≤ y)

3
1 Xay
0 1
2 Amr
1 1
-1 1
2 Xay
1 4
-1 2

Amr
Xay
Amr

Hint

If Xay choose the pair (x, y), he will change it to (a, b) which make a/b as large as possible. 

# The Spot Game

The game of Spot is played on an NxN board as shown below for N = 4. During the game, alternate players may either place a black counter (spot) in an empty square or remove one from the board, thus producing a variety
of patterns. If a board pattern (or its rotation by 90 degrees or 180 degrees) is repeated during a game, the player producing that pattern loses and the other player wins. The game terminates in a draw after 2N moves if no duplicate pattern is produced before
then.

Consider the following patterns:

If the first pattern had been produced earlier, then any of the following three patterns (plus one other not shown) would terminate the game, whereas the last one would not.

## Input and Output

Input will consist of a series of games, each consisting of the size of the board, N (2  N  50)
followed, on separate lines, by 2N moves, whether they are all necessary or not. Each move will consist of the coordinates of a square (integers in the range 1..N) followed by a blank and a character +’ or -’ indicating the addition or removal of a spot
respectively. You may assume that all moves are legal, that is there will never be an attempt to place a spot on an occupied square, nor to remove a non-existent spot. Input will be terminated by a zero (0).

Output will consist of one line for each game indicating which player won and on which move, or that the game ended in a draw.

## Sample input

2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0

## Sample output

Player 2 wins on move 3
Draw

#include<iostream>
#include<cstring>
#include<set>

using namespace std;

char grid[55][55];
set<string> vis;
int n;

int try_to_insert()
{
string str="";
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
str=str+grid[i][j];
}
}
if(vis.count(str)) return 0;
vis.insert(str);
str="";
for(i=n-1;i>=0;i--)
{
for(j=0;j<n;j++)
{
str=str+grid[i][j];
}
}
if(!vis.count(str)) vis.insert(str);
str="";
for(i=n-1;i>=0;i--)
{
for(j=n-1;j>=0;j--)
{
str=str+grid[i][j];
}
}
if(!vis.count(str)) vis.insert(str);
str="";
for(i=0;i<n;i++)
{
for(j=n-1;j>=0;j--)
{
str=str+grid[i][j];
}
}
if(!vis.count(str)) vis.insert(str);
return 1;
}

int main()
{
while(cin>>n&&n)
{
int flag=1,winner,num;
int i,x,y;
char ch;
vis.clear();
memset(grid,'0',sizeof(grid));
for(i=0;i<2*n;i++)
{
cin>>x>>y>>ch;
if(flag==0) continue;
if(ch=='+') grid[x-1][y-1]='1';
else if(ch=='-') grid[x-1][y-1]='0';
if(try_to_insert()==0)
{
flag=0;
num=i+1;
if(i%2==0) winner=2;
else winner=1;
cout<<"Player "<<winner<<" wins on move "<<num<<endl;
}
}
if(flag) cout<<"Draw"<<endl;
}
return 0;
}

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。