Euclid's Game
|
Time Limit: 1000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 4525 |
|
Accepted: 1849 |
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
Source
Waterloo local 2002.09.28
给定两堆石子,二人轮流取子,要求只能从石子数目较大的那一堆取子,取子的数目只能是另一堆石子数目的倍数.最终使得某一堆数目为零的一方为胜.
首先,容易看出,对于每一个局面,要么是先手必胜,要么是后手必胜,最终结果完全由当前局面完全确定.
另外,可以简单罗列一下先手必胜和必败的几种局面(两堆石子初始数目都大于零):
1,有一堆石子数目为一,先手必胜, 1,4, 1,2.
2,两堆石子数目差一,且两堆石子数目都不为一,先手必败(只能使后手面对必胜的局面),如 3,4 5,6 .
3,如果数目较大的那一堆是数目较小那一堆的2倍加减一,且不是上面两种局面,先手必胜,2,5 3,5 3,7.
可是上面这些信息对于解决这个问题还是有一些困难.
再进一步试算数目较小的石子,可以发现,当两堆数目相差较大时,总是先手必胜.
事实上,进一步探讨可以发现下面的结论:
1,N<2*M-1时,先手别无选择,只能使之变为 N-M,M 局面,(易见)如3,5 5,7 7,4...
2,设两堆石子数目为N,M(N>M>0,且N,M互质),则若N>=2*M-1,且N - M ! =1时,先手必胜.要求M,N互质是因为对于M,N有公因数的情形,可以同时除以其公因数而不影响结果.
简单说明一下上面结论2的由来. N>=2*M-1时,先手可使之变为 N%M,M 或N%M+M,M两种局面之一,其中有且只有一个必败局面。注意到如果N%M,M不是必败局面，那么N%M+M,M就是必败局面，因为面对N%M+M,M这个局面，你别无选择，只能在前一堆中取M个使对方面对必胜局面(结论1 )。
据此可设计算法如下:
1.M,N先同时除以它们的最大公因数.(M<N)
2,如果M==0,则返回零;
3,如果M==1,则返回一;
4,如果N>=M*2-1,则返回一
5,令N=M,M=N-M,递归处理
#include <iostream>
using namespace std;
long long gcd(long long a,long long b)
{
if(a==0)
return b;
return gcd(b%a,a);
}
long long Eu(long long m,long long n)
{
if(m==1)
return 1;
if(n-m==1 && m)
return 0;
if(n>=m*2-1)
return 1;
return !Eu(n%m,m);
}
int main()
{
long long m,n,temp;
while (cin>>m>>n && (m||n))
{
long long g=gcd(m,n);
m/=g;
n/=g;
if(m>n)
{
temp=m;
m=n;
n=temp;
}
if(Eu(m,n))
cout<<"Stan wins"<<endl;
else
cout<<"Ollie wins"<<endl;
}
return 0;
}