首页 > 代码库 > hdu 1517 （类巴神博弈）
hdu 1517 （类巴神博弈）
A Multiplication Game
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3977 Accepted Submission(s): 2264
Problem Description
Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.
Input
Each line of input contains one integer number n.
Output
For each line of input output one line either
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.
Sample Input
162 17 34012226
Sample Output
Stan wins. Ollie wins. Stan wins.
Source
University of Waterloo Local Contest 2001.09.22
分析与巴什博弈很类似，将巴神博弈中的加法转化为此处的乘法，进行类比。
显然2~9之间先手赢（实际上此处为一的时候也为先手赢，最少值乘以二就超过了一）
10~18的时候，不管先手怎么安排第一步，后手赢！
要想先手继续赢，则需要在2~9 的基础上乘以18（主要是后面的范围，前面的范围与前
一个必败（胜）态，紧紧相邻即可），此时，不管后手怎么办，都能够通过
接下来的弥补，使有利局势，保证在先手的手里。即要想先手赢，需要在最初的基础上
多次乘以18。同理要想后手赢，需要在10~18的基础上多次乘以18.即判断输入的n除掉
多个18后剩下来的m与9作比较即可！m<=9，先手赢。10<=m<=18,后手赢！
代码如下：
#include<stdio.h>
int main()
{
double n;//此处需要用double型 数据较大，没想到竟然__int64 位竟然都不可以-_-!
while(~scanf("%lf",&n))
{
while(n>18)//循环到最后观察最终剩余的数的范围，在2~9之间为先手的必胜态，10~18为先手的必败态
n/=18;
printf(n<=9?"Stan wins.\n":"Ollie wins.\n");
}
return 0;
}hdu 1517 （类巴神博弈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。