首页 > ACM题库 > HDU-杭电 > HDU 3595-GG and MM[解题报告]HOJ
2014
11-27

HDU 3595-GG and MM[解题报告]HOJ

GG and MM

问题描述 :

GG and MM like playing a game since they are children. At the beginning of game, there are two piles of stones. MM chooses a pile of stones first, which has x stones, and then she can choose a positive number k and remove k*x stones out from the other pile of stones, which has y stones (I think all of you know that y>=k*x – -!). Then it comes the turn of GG, followed the rules above-mentioned as well. When someone can’t remove any stone, then he/she loses the game, and this game is finished.
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~

输入:

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.

输出:

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.

样例输入:

3
1 1
1 1
1 1
1
3 2

样例输出:

MM
GG

#include<cstdio>
int cnt=0;
bool dfs(int a,int b)
{
 if(a<b) a^=b,b^=a,a^=b;
 if(b==0) return 0;
 if(!dfs(b,a%b)){cnt++;return 1;}
 if(a/b>1){cnt+=2;return 1;}
 else {cnt++;return 0;}
}
int main()
{
 int n;
 while(scanf("%d",&n)!=EOF)
 {
 int x,y,a=0,b=0;
 for(int i=0;i<n;i++)
 {
 scanf("%d%d",&x,&y);
 cnt=0;
 if(dfs(x,y)) a=a>cnt?a:cnt;
 else b=b>cnt?b:cnt;
 }
 puts(a>b?"MM":"GG");
 }
 return 0;
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }