Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8313 | Accepted: 3374 |
Description
25 7
11 7
4 7
4 3
1 3
1 0
an Stan wins.
Input
Output
Sample Input
34 12
15 24
0 0
Sample Output
Stan wins
Ollie wins
Source
SolutionⅠ
黄金比例
如果两个数相等,或者两数之比大于斐 波拉契数列相邻两项之比的极限((sqrt(5)+1)/2),则先手胜,否则后手胜。
var a,b:longint;f:boolean; procedure swap();
begin
b:=a xor b;
a:=a xor b;
b:=a xor b;
end; begin
while true do
begin
readln(a,b);
if (a=)and(b=) then halt;
if a>b then swap();
if (a=b)or(b/a>=(sqrt()+)/) then writeln('Stan wins')
else writeln('Ollie wins');
end;
end.
SolutionⅡ
给定两堆石子,二人轮流取子,要求只能从石子数目较大的那一堆取子,取子的数目只能是另一堆石子数目的倍数.最终使得某一堆数目为零的一方为胜.
首先,容易看出,对于每一个局面,要么是先手必胜,要么是后手必胜,最终结果完全由当前局面完全确定.
另外,可以简单罗列一下先手必胜和必败的几种局面(两堆石子初始数目都大于零):
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 )。
解释来源:http://www.cppblog.com/sdz/archive/2010/08/29/125124.html
var a,b:int64;f:boolean; procedure swap();
begin
b:=a xor b;
a:=a xor b;
b:=a xor b;
end; procedure main;
begin
while = do
begin
if a>b then swap();
if (b mod a=)then break;
if (b-a>a) then break;
dec(b,a);
if f=false then f:=true;
if f=true then f:=false;
end;
if f then writeln('Stan wins')
else writeln('Ollie wins');
end; begin
while true do
begin
readln(a,b);
f:=true;
if (a=)and(b=) then halt;
main;
end;
end.