Euclid‘s Game HDU - 1525

Euclid’s Game HDU - 1525

HDU - 1525

题面描述

Problem Description
Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):

25 7
11 7
4 7
4 3
1 3
1 0
an Stan wins.
Input
The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.
Output
For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed.
Sample Input
34 12
15 24
0 0
Sample Output
Stan wins
Ollie wins

翻译

问题描述

两个玩家，斯坦和奥利，开始玩，两个自然数。第一个玩家Stan用两个数字中较大的数减去两个数字中较小的数的倍数，前提是得到的数字必须是非负的。然后，第二个玩家奥利(Ollie)对得到的两个数字做同样的操作，然后是斯坦(Stan)等，交替进行，直到其中一个玩家能够从较大的数字中减去较小的数字的倍数，从而达到0，从而获胜。例如，玩家可以从(25,7)开始:
25 7
11 7
4 7
4 3
1 3
1 0
an Stan wins.
输入
输入由许多行组成。每行包含两个正整数，给出游戏开始的两个数字。斯坦总是开始。
输出
对于每一行输入，输出一行说Stan赢或Ollie赢假设他们都玩得完美。输入的最后一行包含两个零，不应该被处理。

AC代码

#include<stdio.h>
#include<stack>
#include<string.h>
#include<algorithm>
#define inf 0xffffff
using namespace std;

int main()
{
    int m,n;
    while(~scanf("%d%d",&m,&n))
    {
        int flog=0;
        if(m==0&&n==0)
            break;
        int maxa=max(m,n);
        int mina=min(m,n);
        if(maxa>=2*mina)
        {
            printf("Stan wins\n");
        }
        else
        {
            int ans=0;
            while(m%n!=0&&n%m!=0)
            {
                if(m>n&&m<2*n)
                {
                    m=m-n;
                    ans++;
                }
                else if(n>m&&n<2*m)
                {
                    n=n-m;
                    ans++;
                }
                else if(n>2*m||m>2*n)
                {
                    flog=1;
                    if(ans%2==0)
                        printf("Stan wins\n");
                    else
                        printf("Ollie wins\n");
                    break;
                }
            }
            if(ans%2==0&&flog==0)
            {
                printf("Stan wins\n");
            }
            else if(ans%2!=0&&flog==0)
                printf("Ollie wins\n");
        }
    }
    return 0;
}

本文地址：https://blog.csdn.net/sugarsong/article/details/109255578