题解 - Vijos

2

猫粮寸断 LV 10 @ 2018-11-02 14:25:44

//游戏过程是模拟求gcd过程的，知道这点后可以开始做了
//若
//1.a%b==0，显然此时当前的人直接胜利
//2.a/b大于2，则当前的人有两种以上方案，一定有一种可以保证他胜利
//因此模拟gcd判断就可以了
#include<iostream>
using namespace std;
int main()
{
    int c,now;
    long long a,b,temp;
    cin>>c;
    while(c--)
    {
        now=1;
        cin>>a>>b;
        if(a<b)
        {
            temp=a;
            a=b;
            b=temp;
        }
        while(b)
        {
            if(a/b>=2||a%b==0)
             break;
            temp=a;
            a=b;
            b=temp%b;
            now=now^1;
        }
        if(now)
         cout<<"Stan wins"<<endl;
        else
         cout<<"Ollie wins"<<endl;
    }
    return 0;
}

2

sqs LV 10 @ 2009-07-18 08:57:50

先判断保证 m大于n，

因为当m-n>=n时，当前操作者对之后的步数有调整空间，

所以谁轮到的数字可以构成这种结构谁就能获胜。

若m-n=n情况的位置,记录之前的步数，

通过步数的奇偶性来判断谁获胜。

1

王瑞程 LV 8 @ 2017-07-12 20:29:30

var
    i,c,a,b,t:longint;
    winner:boolean;
begin
    readln(c);
    for i:=1 to c do
    begin
        winner:=false;
        readln(a,b);
        if a<b then begin t:=a; a:=b; b:=t; end;
        while a mod b>0 do
        begin
            if a div b =1 then winner:=not winner else break;
            t:=a mod b; a:=b; b:=t;
        end;
        if winner then writeln('Ollie wins') else writeln('Stan wins');
    end;
end.

被坑了，没发现初始给的M不一定大于N，害的我WA了好几次还耽误半天......

0

Hory LV 10 @ 2016-09-05 19:55:19

明明是个数论题。。。

0

Hory LV 10 @ 2016-09-05 19:54:57

记录信息
评测状态    Accepted
题目  P1208 欧几里德的游戏
递交时间    2016-09-05 19:53:28
代码语言    C++
评测机 ShadowShore
消耗时间    0 ms
消耗内存    564 KiB
评测时间    2016-09-05 19:53:29
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10
Accepted, time = 0 ms, mem = 564 KiB, score = 100
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
    int c;
    cin>>c;
    for (int i=1;i<=c;i++)
    {
        int m,n;
        cin>>m>>n;
        if (m < n) swap(n,m);
        int f = 1;
        while ( m/n == 1 && m%n)
        {
            int t = m%n;
            m = n;
            n = t;
            f = -f;
        }
        if (f == 1)
            cout<< "Stan wins"<<endl;
        else cout<< "Ollie wins"<<endl;
    }
    return 0;
}```

0

zone LV 10 @ 2016-08-06 10:50:23

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long lg;
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
 

int n;

bool pd(int a,int b)
{
    if(a==b) return 1;
    if(a<b)
    {
        a=a^b;
        b=a^b;
        a=a^b;
    }
    if(b==0) return 1;
    if(a/b<2)
        return !pd(a-b,b);
    return 1;
    
}


int main(int argc, char** argv)
{
    int a,b;
    cin>>n;
    while(n--)
    {
       cin>>a>>b;
       if(pd(a,b))
        cout<<"Stan wins"<<endl;
       else
        cout<<"Ollie wins"<<endl;   
    }
    return 0;
}

0

三次元❤堕天逗比 LV 10 @ 2016-03-23 16:53:36

编译成功

foo.cpp: In function 'int main()':
foo.cpp:11:31: warning: unknown conversion type character 'l' in format [-Wformat=]
{ scanf("%lld%lld",&a,&b);
^
foo.cpp:11:31: warning: unknown conversion type character 'l' in format [-Wformat=]
foo.cpp:11:31: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 552 KiB, score = 10

Accepted, time = 0 ms, mem = 552 KiB, score = 100

0

TenderRun LV 10 @ 2015-10-10 19:08:21

记录信息
评测状态 Accepted
题目 P1208 欧几里德的游戏
递交时间 2015-10-10 19:08:05
代码语言 C++
评测机 VijosEx
消耗时间 44 ms
消耗内存 524 KiB
评测时间 2015-10-10 19:08:06
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:11:28: warning: unknown conversion type character 'l' in format [-Wformat=]
{ scanf("%lld%lld",&a,&b);
^
foo.cpp:11:28: warning: unknown conversion type character 'l' in format [-Wformat=]
foo.cpp:11:28: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 4 ms, mem = 520 KiB, score = 10
测试数据 #1: Accepted, time = 6 ms, mem = 524 KiB, score = 10
测试数据 #2: Accepted, time = 5 ms, mem = 524 KiB, score = 10
测试数据 #3: Accepted, time = 6 ms, mem = 524 KiB, score = 10
测试数据 #4: Accepted, time = 5 ms, mem = 520 KiB, score = 10
测试数据 #5: Accepted, time = 6 ms, mem = 520 KiB, score = 10
测试数据 #6: Accepted, time = 5 ms, mem = 524 KiB, score = 10
测试数据 #7: Accepted, time = 6 ms, mem = 520 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #9: Accepted, time = 1 ms, mem = 520 KiB, score = 10
Accepted, time = 44 ms, mem = 524 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
char s[3][100]={"Ollie wins","Stan wins"};
int main()
{
int n;
long long a,b;
scanf("%d",&n);
while(n--)
{ scanf("%lld%lld",&a,&b);
if(a==0&&b==0)break;
if(a<b){
a=b+a;
b=a-b;
a=a-b;
}
for(int i=1;;i++){
if((int)(a/b)>=2||a==b){
printf("%s\n",s[i%2]);
break;
}
a-=b;
a=b+a;
b=a-b;
a=a-b;
}
}

}

0

ocacs1 LV 9 @ 2015-07-19 16:14:56

测试数据 #0: Accepted, time = 15 ms, mem = 280 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 280 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 276 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 280 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 276 KiB, score = 10
Accepted, time = 60 ms, mem = 280 KiB, score = 100
呵呵哒，AC！

0

一方T行 LV 10 @ 2014-09-06 00:15:15

program p1208;
var n,i:longint;
a,b:int64;
//
function gcd(a,b:int64):boolean;
begin
if (b=0) then exit(false)
else if (a div b>1) then exit(true)
else gcd:=not(gcd(b,a mod b));
end;
//
begin;
read(n);
for i:=1 to n do
begin
read(a,b);
if a<b then begin a:=a xor b;b:=a xor b;a:=a xor b;end;
if gcd(a,b) then writeln('Stan wins')
else writeln('Ollie wins');
end;
end.

0

snophy LV 8 @ 2014-07-30 22:04:31

废话不多说，贴代码
var
i,t,c,n,m,step:longint;
begin
readln(c);
for i:=1 to c do
begin
readln(n,m);
step:=0;
while (n>0) and (m>0) do
begin
inc(step);
if m>n then
begin
t:=m;
m:=n;
n:=t;
end;
if n div m>1 then
break;
n:=n mod m;
end;
if odd(step) then
writeln('Stan wins')
else
writeln('Ollie wins');
end;
end.

0

zjhl2 LV 9 @ 2013-08-23 14:36:00

var
m,n,i,a,k,y:longint;
begin
readln(k);
for i:=1 to k do
begin
y:=1;
readln(m,n);
repeat
if m<n then
begin
a:=m; m:=n; n:=a;
end;
if (m div n>1)or(m mod n=0) then
begin
if y=1 then writeln('Stan wins') else writeln('Ollie wins');
break;
end;
m:=m mod n;
y:=-y;
until m=0;
end;
end.

0

wyc4662 LV 10 @ 2010-07-24 14:13:17

博弈论啊……

居然没考虑a=b……幸亏楼下们提醒

2.5星庆祝！

0

jessie LV 7 @ 2009-11-04 21:26:14

Accepted 有效得分：100 有效耗时：0ms

0

雷子涵2 LV 10 @ 2009-10-28 15:54:04

注意A=B 的情况

0

瀑布飞鹰 LV 8 @ 2009-10-22 12:00:32

用那个什么sqrt(5)那个么？？？感觉不好.....

本来想裸奔...看着数据吓着了.....

---|---|---|---|---|---|---|---|---|---|---|---|--

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var a,b,n,i:longint;

function gcd(a,b:longint):boolean;

var t:longint;

begin

if a=b shl 1) then exit(true);

exit(not gcd(b,a-b));

end;

begin

readln(n);

for i:=1 to n do

begin

readln(a,b);

if gcd(a,b) then writeln('Stan wins')

else

writeln('Ollie wins');

end;

end.

0

zhanghanyuan LV 10 @ 2009-10-18 19:47:52

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

晕,怎么过的都不知道,真奇怪

NND,看了楼下题解,无语了，我想多了

0

gsrq LV 10 @ 2009-10-01 16:06:59

var

i,t,n,m,c:longint;

p:real;

begin

readln(c);

for i:=1 to c do

begin

readln(n,m);

p:=(sqrt(5)+3)/2;

t:=trunc(n/p);

if ((n-t

0

prince_hao LV 10 @ 2009-09-16 18:45:52

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

加个1..5000的SB记忆化..

0

尖端才子 LV 10 @ 2009-08-23 22:21:19

恩……是个欧几里得算法+博弈树……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

题解

47 条题解

欧几里德的游戏

信息

状态

开发

支持

题解

47 条题解

欧几里德的游戏

信息

状态

开发

支持

还没有账户？

登录