hdu3595 GG and MM----sg

GG and MMTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 273    Accepted Submission(s): 108


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<cstdio>#include<cstdio>#include<cstring>#include<iostream>#define M 1002using namespace std;int n,sg[M][M],step[M][M];int find(int a,int b){ if(sg[a][b]>=0) return sg[a][b]; if(a>b) swap(a,b); int mi=99999999,ma=0; for(int i=a;i<=b;i+=a) { if(find(a,b-i)==0)//后一步是必败点 { ma=max(ma,step[a][b-i]);//当前点是必胜点，所以要延时 sg[a][b]=sg[b][a]=1; } else mi=min(mi,step[a][b-i]); } if(sg[a][b]==1) { step[a][b]=step[b][a]=ma+1; return 1; } step[a][b]=step[b][a]=mi+1; return sg[a][b]=sg[b][a]=0;}int main(){ memset(sg,-1,sizeof(sg)); for(int i=0;i<=1000;i++) step[0][i]=step[i][0]=sg[i][0]=sg[0][i]=0; while(~scanf("%d",&n)){ int ma=0,ma1=0,a,b; while(n--) { scanf("%d %d",&a,&b); if(a==0||b==0) continue; if(find(a,b)==1) { if(step[a][b]>ma) ma=step[a][b]; } else { if(step[a][b]>ma1) ma1=step[a][b]; } } puts(ma>ma1?"MM":"GG"); } return 0;}