一月17日新生冬季练习赛解题报告G.Play Game 2

我发现我还是蛮喜欢做博弈论的题的  特别能锻炼人的思维

G.Play Game 2

Time Limit: 1000 MS

Memory Limit: 32768 K

 

Total Submit: 95 (50 users)

Total Accepted: 30 (30 users)

Special Judge: No

 

Description

小Stan和小Ollie两个人玩一个叫做乘数的游戏,给出的原数为1,两个人乘的时候可以乘以2到9之间的任何数,现在给出一个数n,判断在两者都采取最优策略的情况下,谁先能够使得乘完之后的数大于等于n,谁就胜利。由小Stan先手。

Input

多组输入数据。

每组输入包涵一个整数n(0<n<2^31).

Output

输出比赛结果:Stan wins. or Ollie wins.

Sample Input

162

17

34012226

Sample Output

Stan wins.

Ollie wins.

Stan wins.

我们这样考虑  想要得到n必须得到什么  然后大脑就像递归一样往前推就会想懂;

 

就跟取石子那个题思维是一样的

 

对于这个题  想要得到n  必须是对手得不到n  而你在他的基础上一定能得到n

所以你必须得到n/18这个数   这样  他无论乘多少都得不到n然而你在他的基础之上就一定能得到n

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    int n;

    while(cin>>n){

    while(n>18)

    {

        if(n%18==0)

            n/=18;

        else

            n=n/18+1;

    }

    if(n<=9)

        cout<<"Stan wins."<<endl;

    else

        cout<<"Ollie wins."<<endl;

    }

    return 0;

}

一月17日新生冬季练习赛解题报告G.Play Game 2

上一篇:hdu 1506 Largest Rectangle in a Histogram


下一篇:一月17日新生冬季练习赛解题报告F.Play Game 1