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.
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。（当你走到此点的时候，如果你无论怎么都输，这个点就叫做必败点。） 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。（当你走到此点的时候，以聪明的走法去走，可以赢对方） 算法实现： 步骤1:将所有终结位置标记为必败点（P点）；（终结位置指的是不能将游戏进行下去的位置） 步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。 题意： 你和一个人玩游戏，给你一个数字n，每次操作可以从2~9中任选一个数字，并把它与p相乘，（游戏开始时p=1） 两人轮流操作，当一个人操作完后p>=n，这个人就是胜者。 解题思路： 由于每次都是从p=1开始的，所以只要判断每个游戏中1为必败点还是必胜点即可。（以下各式 / 均为取上整，可以利用ceil函数） 依照上面所提到的算法，将终结位置，即[n,无穷]标记为必败点； 然后将所有一步能到达此必败段的点标记为必胜点，即[n/9,n-1]为必胜点；（这个地方需要理解下，最小的情况n/9，再*9j即可达到目标，最大的情况n-1，再稍微随意变动可以达到目标） 然后将只能到达必胜点的点标记为必败点，即[n/9/2,n/9-1]为必败点；（对应上面的解释，也是在临界状态无法达成目标）
重复上面2个步骤，直至可以确定1是必胜点还是必败点。
注意：开始时候的p=1，然后stan开始相乘，之后是Ollie.
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; int main() { int n; while(scanf("%d",&n)==1) { int x; for(x=0;n>1;x++) //x=0先寻找必胜点 { if(x&1) n=ceil(n*1.0/2); //必败点最小值的情况 else n=ceil(n*1.0/9); //必胜点最小值的情况 } printf("%s\n",x%2==1?"Stan wins.":"Ollie wins.");//最后当小于等于n的时候判断x是必败点还是必胜点 } }