Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 805 Accepted Submission(s): 367 Problem Descripti ...
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 805 Accepted Submission(s):
367
Many years later, GG and MM find this game is too simple, so they decided to play N games at one time for fun. MM plays first, as the same, and the one on his/her turn must play every unfinished game. Rules to remove are as same as above, and if someone cannot remove any stone (i.e., loses the last ending game), then he/she loses. Of course we can assume GG and MM are clever enough, and GG will not lose intentionally, O(∩_∩)O~
Input The input file contains multiply test cases (no more than 100).
The first line of each test case is an integer N, N<=1000, which represents there are N games, then N lines following, each line has two numbers: p and q, standing for the number of the two piles of stones of each game, p, q<=1000(it seems that they are so leisure = =!), which represent the numbers of two piles of stones of every game.
The input will end with EOF.
Output For each test case, output the name of the winner.
Sample Input 3 1 1 1 1 1 1 1 3 2
Sample Output MM GG
Author alpc95
Source 2010 ACM-ICPC Multi-University Training Contest（16）——Host by NUDT
Recommend zhengfeng | We have carefully selected several similar problems for you: 3600 3593 3599 3598 3594 題意：一共有n個游戲，每一個游戲有兩堆石子，一次移動可以從大的那堆石子里拿小的那堆石子的整數倍的石子。 只要是可以操作的游戲都要進行操作，不能進行操作的人負。 比較神的博弈 模型是Every-SG肯定是沒問題，框架按套路寫就可以 有一個比較顯然的結論 設兩個數為$(x,y)$，那麼當$\frac{y}{x}>1$，此時先手必勝，因為先手可能通過控制倍數來控制接下來步數的奇偶性
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> const int MAXN=1001; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int a[MAXN],b[MAXN],SG[MAXN][MAXN],step[MAXN][MAXN]; int GetSG(int x,int y) { if(x>y) std::swap(x,y); if(SG[x][y]!=-1) return SG[x][y]; if(!x||!y) return SG[x][y]=step[x][y]=0; int willx=y%x,willy=x; int k=y/x; if(k==1) { SG[x][y]=GetSG(willx,willy)^1; step[x][y]=step[willx][willy]+1; return SG[x][y]; } else { step[x][y]=GetSG(willx,willy)+step[willx][willy]+1; return SG[x][y]=1;//此時先手必勝 } } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(SG,-1,sizeof(SG)); int N; while(scanf("%d",&N)!=EOF) { int ans=0; for(int i=1;i<=N;i++) { int x=read(),y=read(); if(x>y) std::swap(x,y); GetSG(x,y); ans=std::max(ans,step[x][y]); } puts(ans%2?"MM":"GG"); } return 0; }
