[原创]HDU 1517 A Multiplication Game [。。]【博弈】

2016-10-27 16:17:26 Tabris_ 阅读数：239

博客爬取于2020-06-14 22:42:58
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52946902

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1517

-------------------------------.
A Multiplication Game

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5345 Accepted Submission(s): 3048

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.

Sample Input
162
17
34012226

Sample Output
Stan wins.
Ollie wins.
Stan wins.

Source
University of Waterloo Local Contest 2001.09.22

Recommend
LL

-------------------------------.

题目大意：就是给你数n 两个人轮流对x（初始为1）乘上一个[2,9]之间的一个数字 最先得到x≥n的人获胜

解题思路：
这种题 很显然是博弈 但是又不是几个常见的模型
所以找一下其中的必胜态和必败态

首先对于[n,+∞]一定是必胜态 ，没有问题 ；
那么能够一步到达这里的一定是必败态
那就是[ceil(n/9),n-1];
然后不管怎么样一步只能到达必败态的位置一定是必胜态；
那就是[ceil(n/2),n-1];

之后这样的话我们就可以暴力的枚举到最后 看一看1这个位置是必胜态还是必败态就好了

附本题代码
-------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# include <bits/stdc++.h>

int main()
{
    LL n;
    while(~scanf("%I64d",&n))
    {
        int i;
        for(i=0;n>1;i++)
        {
            if(i&1) n = ceil(n*1.0/2);
            else    n = ceil(n*1.0/9);
        }
        puts(i&1?"Stan wins.":"Ollie wins.");
    }
    return 0;
}