tjut 3595

#include<cstdio> #include<cstdio> #include<cstring> #include<iostream> #define M 1002 using 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; }