POJ2505A multiplication game

易水人去，明月如霜。

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.

题目大意：两个人轮流玩游戏，Stan先手，数字 p从1开始，Stan乘以一个2-9的数，然后Ollie再乘以一个2-9的数，直到谁先将p乘到p>=n时那个人就赢了，而且轮到某人时，某人必须乘以2-9的一个数。

解题思路：

博弈，找规律，首先我们容易得到在

[2,9]这个区间，是Stan必胜

[10,18]这个区间，是Ollie必胜

那么下个区间左边肯定是[18+1，？]，是Stan必胜

区间闭应该填一个什么数呢，因为18是一个必败点，所以轮到Stan开始，那么他可以乘以一个9，即18*9之内，Stan都必胜

我们可以将18看成9*2，也就是说Stan越想接近N，Ollie肯定越不想他达到N

所以下个区间为[18+1,9*2*9]，其实找规律也能找出一个这样的规律

[9*2*9+1，9*2*9*2]，Ollie必胜

[9*2*9*2+1，9*2*9*2*9]，Stan必胜

代码：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> const int MAXN=10000; using namespace std; int main (void) { long long num; while(~scanf("%lld",&num)) { if(num<=9) { printf("Stan wins.\n"); continue; } if(num>9&&num<=18) { printf("Ollie wins.\n"); continue; } while(num>18) { num=(num-1)/18+1; } if(num<=9) { printf("Stan wins.\n"); continue; } if(num>9&&num<=18) { printf("Ollie wins.\n"); continue; } } return 0; }