2014
02-17

# Paper Cutting Game

Lily and Lucy are playing a new paper cutting game.
The game uses a rectangular paper that consists of W*H grids.At first,there is only a sheet of W*H paper. In each turn,One player picks up cut one piece of paper and cut it into several pieces of equal rectangular sections,and puts them back. Lily can only cut horizontally and Lucy can only cut vertically,keeping every grids unbroken.The one who can’t cut the paper loses.
Now given you a sheet of W*H paper.We know Lily always plays first.We can assume that both player are clever enough to make the right move.Could you help Lily to make sure if she can win the game?

Input contains multiple cases.
Each test case starts with two integerW(1<=N<=1000) ,H(1<=H<=1000) ,says that there is a sheet of W*H paper at firsst.

Input contains multiple cases.
Each test case starts with two integerW(1<=N<=1000) ,H(1<=H<=1000) ,says that there is a sheet of W*H paper at firsst.

1 1
2 2
4 2
6 4

Lose
Lose
Win
Lose
Hint
Hint
In sample 3,we have a sheet of 4*2 paper.Lily may cut the paper into 2*2,2*2 or 1*2,1*2,1*2,1*2.
Obviously Lily would choose the first kind of move.Lucy then can only pick up one 2*2 paper and cut it into 2*1,2*1.We know that Lily is sure to win.


hdu 2869 Paper Cutting Game

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL Mod= 1e9+7;
int N, M, tot;
int p[100], a[1000];
void getp( )
{
p[0]=2;
for( int i=3; i<40; i+=2 ){
if( !a[i] ){
for( int j=i+i; j<1000; j+=i )
a[j]=1;
}
}
for( int j=3; j<1000; j+=2 )
if( !a[j] )
p[++tot]=j;
}
int AC( int x )
{
int ans=0;
for( int i=0; p[i]&&p[i]<=x; ++ i ){
while( x%p[i]==0 ){
ans++;
x/=p[i];
}
}
return ans;
}
int main( )
{
getp();
while( scanf("%d%d", &N,&M)==2 ){
if( AC( N )<=AC(M) )puts( "Lose" );
else puts( "Win" );
}
return 0;
}

poj 2311

SG应用的场景

 游戏有两个人参与，二者轮流做出决策。且这两个人的决策都对自己最有利。 

当有一人无法做出决策时游戏结束，无法做出决策的人输。

无论二者如何做出决策，游戏可以在有限步内结束。 

游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。 

任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL Mod= 1e9+7;
int N, M;
int sg[205][205];
int mex(int x, int y)
{
if( sg[x][y]!=-1 )return sg[x][y];
bool re[205]={0};
int i;
for( i=2;i<=x/2;++i ){
re[mex(i, y)^mex(x-i, y)]=1;
}
for( i=2;i<=y/2;++i ){
re[mex(x, i)^mex(x, y-i)]=1;
}
i=0;
while( re[i] )++i;
return sg[x][y]=i;
}
int main( )
{
memset( sg, -1 , sizeof sg);
sg[2][2]=sg[2][3]=sg[3][2]=0;
while( scanf("%d%d", &N,&M)==2 ){
if( N==1 || M==1 )puts("LOSE");
else if( mex( N, M ) )puts( "WIN" );
else puts("LOSE");
}
return 0;
}