首页 > 代码库 > hdu 1525 找规律博弈 (根据每一步的必然性以及可选择性决策)
hdu 1525 找规律博弈 (根据每一步的必然性以及可选择性决策)
题目来源:
http://acm.hdu.edu.cn/showproblem.php?pid=1525
题意: 给出两个数,a和b,将大的数中,减去若干b的倍数,最终有一个数为0的话就胜了。
分析: 两个数a和b, 不妨设(a > b),总会出现的一个局面是b,a%b,这是必然的,如果a>=b&&a<2*b,那么只有一种情况,直接到b,a%b。否则有多种情况。
a / b == 1 即a Ε [b , 2b) , 下一步 只能到达 (b , a - b)
a / b >= 2 时, 先手可以选择让谁来面对 (b , a%b)这个局势, 显然先手足够聪明, (b , a % b) 这个局势谁胜谁负 已经清楚, 所以先手必胜。
代码如下:
int main(){ int a , b ; while(scanf("%d%d", &a , &b ) != EOF && (a + b) ){ if(a > b ) swap(a , b) ; int flag = 1; while(1){ if( a == 0 || b % a == 0 || b / a >= 2) break; int t = a; a= b - a ; b = t; flag = !flag ; } if(flag) puts("Stan wins"); else puts("Ollie wins") ; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。