首页 > 代码库 > 博弈１

博弈１

2024-09-17 09:19:37   217人阅读


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种，我们拿样例来说：34和12需要34/12=2步，然后是34%12=10,12,此时需要12/10=1步，此时变成10,2。这样５次就能够减成０了。

显然我们可以把这个看做有３堆石子，分别为２，１，５，每次两个人能轮流在一堆中拿任意个但必须得从第一堆开始往后那（拿完一堆才能拿第二堆）

我们只需导论下情况：

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

２．如果所有堆的石子个数都等于１，那么就看堆数的奇偶。

#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;
}

 

博弈１


联系
我们