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;
}