HDU - 2869 - Paper Cutting Game【博弈】题解

比眉伴天荒 2021-07-24 21:55 332阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2 .代码

### 1.题目 ###

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**  
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.  
**Output**  
For each test case, if Lily can win the game output “Win”,otherwise output “Lose”.  
**Sample Input**  
1 1  
2 2  
4 2  
6 4  
**Sample Output**  
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.

### 2 .代码 ###

#include<iostream>
    #include<cstdio>
    using namespace std;
    int cut(int n)
    { 
    	for(int i=2;i<=n;i++)
    	{ 
    		if(n%i==0)
    		 return n/i;
    	}
    }
    int main()
    { 
       int w,h;
       while(cin>>w>>h)
       { 
       	  int flag;
          while(1)
    	  { 
    	     w=cut(w);
    		 if(w==1)
    		 { 
    		 	flag=0;
    		 	break;
    	     }	
    	     h=cut(h);
    	     if(h==1)
    	     { 
    	     	flag=1;
    	     	break;
    		 }
    	  }	
    	  if(flag)
    	   cout<<"Win"<<endl;
    	  else 
    	   cout<<"Lose"<<endl;
       }	
       return 0;
    }