注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]欧几里德的游戏  

2015-08-07 17:24:01|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:博弈论,更相减损术。

Link&Limit


        [洛谷1290]
        时间限制:1000ms  空间限制:131072kb

Description


        欧几里德的两个后代Stan和Ollie正在玩一种数字游戏,这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N,从Stan开始,从其中较大的 一个数,减去较小的数的正整数倍,当然,得到的数不能小于0。然后是Ollie,对刚才得到的数,和M,N中较小的那个数,再进行同样的操作……直到一个 人得到了0,他就取得了胜利。下面是他们用(25,7)两个数游戏的过程:
        Start:25 7
        Stan:11 7
        Ollie:4 7
        Stan:4 3
        Ollie:1 3
        Stan:1 0
        Stan赢得了游戏的胜利。
        现在,假设他们完美地操作,谁会取得胜利呢?

Input Format


        第一行为测试数据的组数C。下面有C行,每行为一组数据,包含两个正整数M, N(M, N不超过长整型)。

Output Format


        对每组输入数据输出一行,如果Stan胜利,则输出“Stan wins”;否则输出“Ollie wins”.

Sample Input #1


2
25 7
24 15

Sample Output #1


Stan wins
Ollie wins

        可以发现本题的博弈过程很像更相减损术。画出sg函数的推理图之后,我们可以发现如下规律(假定a为较大的数):
        1、如果a ≥ 2b(也就是说,可以进行至少两步操作),那么该状态是获胜状态。
        2、如果a < 2b(也就是说,只能进行一步操作),那么该状态由(b,a-b)状态推导而来。
        有了这两个规律,我们就可以作出解答了。

#include <stdio.h>
int tcase,n,m;
short sg(int a,int b)
{
if(!a || !b) return 0;
if(a>=(b<<1)) return 1;
return !sg(b,a-b);
}
int main()
{
int t;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d%d",&n,&m);
if(n<m) { t = n; n = m; m = t;}
if(n>=(m<<1)) printf("Stan wins\n");
else if(sg(n,m)) printf("Stan wins\n");
else printf("Ollie wins\n");
}
return 0;
}

  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018