POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4106    Accepted Submission(s): 1947


Problem 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 1215 240 0
 
Sample Output
Stan winsOllie wins
 

Source


问题链接POJ2348 UVa10368 HDU1525 Euclid's Game


问题描述参见上文。

问题分析

  这是一个博弈问题。有以下几个要点:

  1.开始时,让a>b;

  2.若a和b有0,则先手胜;

  3.若a%b=0,则当前玩家胜;

  4.若a/b>1,则当前玩家可以胜(当前玩家知道<b,a%b>是否必胜,若不是则将<a,b>变为<a%b,b>即可)

  5.若b<a<2*b,则一步一步模拟下去。

程序说明:(略)

参考链接:(略)


AC的C++语言程序:

/* POJ2348 UVa10368 HDU1525 Euclid's Game */

#include <iostream>

using namespace std;

int main()
{
    int a, b;

    while(cin >> a >> b && (a || b)) {
        bool Stanwins = true;

        if(a < b)
            swap(a, b);
        while(b) {
            if(a % b == 0 || a / b > 1)
                break;
            a = a - b;
            swap(a, b);
            Stanwins = !Stanwins;
        }
        if(Stanwins)
            cout << "Stan wins" << endl;
        else
            cout << "Ollie wins" << endl;
    }

    return 0;
}


 
版权声明:本文为tigerisland45原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/tigerisland45/article/details/72232018

智能推荐

RIP/DHCP/ACL综合实验

组播: 加入组的组成员才会接受到消息,只需要将流量发送一次到组播地址 减少控制面流量,减少头部复制, RIP1  广播   有类  不支持认证 RIP2  组播   无类  (支持VLAN)、支持认证 所有距离矢量路由协议:具有距离矢量特征的协议,都会在边界自动汇总 控制平面  路由的产生是控制平面的流量 数据平面  ...

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

猜你喜欢

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...