有兩個(gè)玩家,Stan 和 Ollie, 在玩游戲。初始有兩個(gè)自然數(shù)。Stan是先手，每次把大的數(shù)字減去小的數(shù)字的任意倍數(shù)，但是不能使數(shù)字變成負(fù)數(shù)。然后Ollie進(jìn)行同樣的操作，直到有一個(gè)玩家使一個(gè)數(shù)字變?yōu)榱恪?br /> 例如，初始時(shí)數(shù)字為(25,7):
25 7
11 7
4 7
4 3
1 3
1 0
這樣Stan贏

Input

輸入數(shù)據(jù)包含多行，每行兩個(gè)正整數(shù)

Output

對(duì)于每組數(shù)據(jù)，加入先手贏，輸出Stan wins,否則輸出Ollie wins。最后一行為0 0，這一行不要處理

Sample Input

34 12 15 24 0 0

Sample Output

Stan wins Ollie wins

題意：?
兩個(gè)數(shù)，兩人輪流操作，大數(shù)可以減去小數(shù)的整數(shù)倍（不能為負(fù)），先到0者為贏。

對(duì)某個(gè)狀態(tài)(a, b) a >= b?
最簡單的情況，如果a%b == 0, 則先手必贏。?
a > 2*b時(shí)，也是先手必贏，因?yàn)?a%b+b, b)狀態(tài)必定與(a%b, b)相反，(a, b)可以轉(zhuǎn)移到其中的必?cái)B(tài)。?
a < 2*b時(shí)，只能轉(zhuǎn)移到(a-b, b)，狀態(tài)與其相反， 繼續(xù)向下轉(zhuǎn)移即可獲知當(dāng)前狀態(tài)。

#include <cstdio> #include <algorithm> using namespace std;int main(int argc, char const *argv[]) {int a, b;while(scanf("%d%d", &a, &b), a&&b){if(a < b)swap(a, b);bool win = true;while(1){if(a % b == 0 || a >= b << 1)break;a -= b;swap(a, b);win = !win;}if(win)puts("Stan wins");elseputs("Ollie wins");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU1525 Euclid's Game 【欧几里得博弈】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。