我发现我还是蛮喜欢做博弈论的题的 特别能锻炼人的思维
|
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;
}
原文：http://www.cnblogs.com/zhanzhao/p/3525663.html