HDU1525 Euclid's Game
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.
InputThe input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.OutputFor 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
题意：
两人博弈，给出两个数a和b，较大数减去较小数的任意倍数，结果不能小于0，将两个数任意一个数减到0的为胜者。
错误思路：
最开始我是这样想的：(a,b)->(b,a%b)，算一个转移，中间可以减a/b次；(b,a%b)->（a%b,b%(a%b)）需要..次。把每一个转移看成一个堆，那么每堆可以任选，就成了Nim博弈了。代码如下：
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
int Xor,a,b;
while(~scanf("%d%d",&a,&b)){
if(a==&&b==) return ;
Xor=;
while(true){
if(a==||b==) break;
if(a<b) swap(a,b);
Xor=Xor^(a/b);
a=a%b;
}
if(Xor) printf("Stan wins\n");
else printf("Ollie wins\n");
} return ;
}
但是这样做是有问题的，因为Nim博弈是任选一堆的任意个，而这样转化的从前往后的堆里选任意个。所以不一样。
正确打开方式： 假设a大于b a == b. N态 a%b == 0. N态
a >= 2*b，先手能决定谁取(b,a%b),并且知道(b,a%b)是P态还是N态. N态
b<a<2*b, 只能 -->(b,a-b) , 然后再进行前面的判断.
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
int num,a,b;
while(~scanf("%d%d",&a,&b)){
if(a==&&b==) return ;
num=;
while(true){
if(a<b) swap(a,b);
if(a%b==||b==) break;
if(a>=*b) break;
a=a%b;
num++;
}
if(num&) printf("Stan wins\n");
else printf("Ollie wins\n");
} return ;
}
最新文章
- Flex DataGrid可编辑对象实现Enter跳转
- JNI支持C++与C的区别
- JavaScript学习12 JS中定义对象的几种方式
- 【POJ 1743】Musical Theme
- jQueryEasyUI
- 如何清除sql server日志
- php 未配置curl
- LINUX HA:Pacemaker + Corosync初配成功
- Oracle EBS-SQL (WIP-13):检查任务组件未选MRP净值.sql
- 5.7.1.3 Global 对象的属性
- 我的代码-statistic analysis
- JavaScript的对象详解
- fiddler模拟返回
- Fatal NI connect error 6413的解决办法 http://www.itpub.net/thread-107518-1-1.html
- Ps—导出：sql作业配合ps导出csv文件
- [转]如何将PHP作为Shell脚本语言使用
- python面向对象总结！
- python3 scrapy 爬取腾讯招聘
- 连接本地websocket服务延迟的问题
- 【UVA】1594 Ducci Sequence（纯模拟）