首页 > 代码库 > [求PN点] poj 2505 A multiplication game

[求PN点] poj 2505 A multiplication game

2024-07-04 16:07:01   221人阅读

题目链接：

http://poj.org/problem?id=2505

A multiplication game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5098 Accepted: 2573

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.

Source

Waterloo local 2001.09.22

[Submit]   [Go Back]   [Status]   [Discuss]


题目意思：

给一个n,两个人轮流玩游戏，从p=1开始，每次可以选择乘以2或者9，谁第一次到达n赢，假设两人都足够聪明。

1 < n < 4294967295

解题思路：

找P必败点，N必赢点

代码解释的很详细：

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

int n;

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   while(~scanf("%d",&n))
   {
       int ans=0; //必输
       int cur=n-1;

       while(cur>=1)
       {
           if(!ans) //后面是必输的状态
               cur/=9;  //在cur/9+1~cur内的人肯定选择*9 获得必胜
           else  //后面是必赢
                cur/=2; //至少要选择*2
          // printf("ans:%d cur:%d\n",ans,cur);
           //system("pause");
           ans^=1;
       }
       if(ans)
            printf("Stan wins.\n");
       else
            printf("Ollie wins.\n");

   }
   return 0;
}



联系
我们