NUC1445 Euclid's Game【博弈】

时间限制: 1000ms 内存限制: 65535KB

问题描述

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):

an Stan wins.

输入描述

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.

输出描述

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.

样例输入

34 12
15 24
0 0

样例输出

Stan wins
Ollie wins

来源

Waterloo local 2002.09.28

问题分析：（略）

这个问题和《POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】》是同一个问题，代码拿过来用就AC了。

程序说明：参见参考链接。

参考链接：POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

题记：程序做多了，不定哪天遇见似曾相识的。

AC的C++程序如下：

/* POJ2348 UVa10368 HDU1525 Euclid's Game */  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
{  
    int a, b;  
  
    while(cin >> a >> b && (a || b)) {  
        bool Stanwins = true;  
  
        if(a < b)  
            swap(a, b);  
        while(b) {  
            if(a % b == 0 || a / b > 1)  
                break;  
            a = a - b;  
            swap(a, b);  
            Stanwins = !Stanwins;  
        }  
        if(Stanwins)  
            cout << "Stan wins" << endl;  
        else  
            cout << "Ollie wins" << endl;  
    }  
  
    return 0;  
}