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.
题意 lily 切矩形的长 lucy切矩形的宽 ,要求必须得均分,不能切的就输了
题解:反正谁也不影响谁,自己切自己的就是了
找一下大于1的最小的因子就行了 我是用模拟
我感觉这类博弈的一般可能会有个直接的结论,反正数据范围挺小的
就直接水过了吧。。。
#include <bits/stdc++.h>
#define maxn 1000+5
#define INF 0x3f3f3f3f
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(scanf("%d%d",&w,&h)!=EOF){
int flag=-1;
while(1){
w=cut(w);
if(w==1){
flag=0;
break;
}
h=cut(h);
if(h==1){
flag=1;
break;
}
}
if(flag)printf("Win\n");
else printf("Lose\n");
}
}