程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1525 Euclids Game (博弈)

HDU 1525 Euclids Game (博弈)

編輯:C++入門知識

兩個數a和b,總會出現的一個局面是b,a%b,這是必然的,如果a>=b&&a<2*b,那麼只有一種情況,直接到b,a%b。否則有多種情況。
對於對於a/b==1這種局面,只可能到b,a%b,沒有選擇。而a/b>=2的話,先手可以選擇由誰面對b,a%b這樣的局勢
顯然選手足夠聰明b,a%b誰必勝必敗已經清楚,先手在a/b>=2的局面必勝
[cpp]
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<cmath> 
#include<vector> 
#include<string> 
#include<map> 
#define LL long long 
#define N 1000000 
#define inf 1<<20 
using namespace std; 
int main(){ 
    int a,b; 
    while(scanf("%d%d",&a,&b)!=EOF&&a+b){ 
        if(a<b) 
            swap(a,b); 
        bool stan=true; 
        while(1){            
            if(b==0||a%b==0||a/b>=2) break; 
            int t=a; 
            a=b; 
            b=t-a; 
            stan=!stan; 
        } 
        if(stan) 
            printf("Stan wins\n"); 
        else www.2cto.com
            printf("Ollie wins\n"); 
    } 
    return 0; 

     

作者:ACM_cxlove

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved