首页 > 代码库 > 博弈1

博弈1


Euclid‘s Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2907    Accepted Submission(s): 1335


Problem Description
Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7): 

25 7
11 7
4 7
4 3
1 3
1 0 

an Stan wins. 

 

 

Input
The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.
 

 

Output
For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed. 

 

 

Sample Input
34 12
15 24
0 0
 

 

Sample Output
Stan wins
Ollie wins
 

题目给出了两个正数a.b

每次操作,大的数减掉小的数的整数倍。一个数变为0 的时候结束。

谁先先把其中一个数减为0的获胜。问谁可以赢。Stan是先手。

思路:我们把a当成是大的数(当b比a小就交换),a要减b的倍数直到减到a<b也就是a=a%b,需要的步骤可能有a/b种,我们拿样例来说:34和12需要34/12=2步,然后是34%12=10,12,此时需要12/10=1步,此时变成10,2。这样5次就能够减成0了。

显然我们可以把这个看做有3堆石子,分别为2,1,5,每次两个人能轮流在一堆中拿任意个但必须得从第一堆开始往后那(拿完一堆才能拿第二堆)

我们只需导论下情况:

1两个人谁先遇到堆里石子个数大于1的谁就能赢

2.如果所有堆的石子个数都等于1,那么就看堆数的奇偶。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int a,b,t;
    vector<int > v;
    while(scanf("%d%d",&a,&b)&&(a>0||b>0))
    {
          v.clear();
         if(a<b)
         {
              t=a;
              a=b;
              b=t;
         }
         while(a%b!=0)
         {
             v.push_back(a/b);
             t=a%b;
             a=b;
             b=t;
         }
         int flag=0;
         for(int i=0;i<v.size();i++)
         {
             if(i%2==0&&v[i]>1)
             {
                 flag=1;
                 break;
             }
             if(i%2==1&&v[i]>1)
             {
                 flag=2;
                 break;
             }
         }
         if(flag==1)
             printf("Stan wins\n");
         else if(flag==2)
             printf("Ollie wins\n");
         else{
             if(v.size()%2==0)
                  printf("Stan wins\n");
             else
                printf("Ollie wins\n");
         }
    }
    return 0;
}

 

博弈1