我发现我还是蛮喜欢做博弈论的题的 特别能锻炼人的思维
G.Play Game 2 | |||||
| |||||
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;
}