poj2311 Cutting Game-----sg
#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;int sg[210][210];int dfs(int n,int m){ if(sg[n][m]>=0) return sg[n][m]; bool g[210]={0}; for(int i=2;i<=n/2;i++) { g[dfs(i,m)^dfs(n-i,m)]=1; } for(int i=2;i<=m/2;i++) { g[dfs(n,i)^dfs(n,m-i)]=1; } for(int i=0;;i++) if(g[i]==0) return sg[n][m]=i;}int main(){ memset(sg,-1,sizeof(sg)); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(dfs(n,m)>0) puts("WIN"); else puts("LOSE"); }}
