hdu 1525

文章目錄

• • Problem Description
  • 題意：
  • 題解：
  • 代碼：

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

題意：

n和m兩個數，兩個人輪流進行操作，每次可以剪去i*min（n，m），i自定（剪去n和m中最小數的倍數），有一個數減到0即為勝利，問先手后手誰先贏

題解：

非正式解答：
一看是博弈論我就開始搜索我腦中的知識（發現為空）
直覺告訴我肯定有規律和公式，我便自造數據多次實驗，最終發現最先遇到一個數是另一個數的兩倍以上時，即可以成功（也就是（n/m>1），此處n>m）,特殊情況是n和m相同時也是誰遇到誰贏。綜合下就是：誰遇到n/m!=1時，誰就贏。
為什么呢？我是這么理解的，當遇到n/m>1時，此人可以選擇減一個m，也可以選減多個m，而這對后面的情況是有影響的，而總有一種情況是對自己有利的，只要按照這個方向走，一定能贏（多局試驗后得出）
當然如果全程n/m==1，那么雙方的操作都是固定的，沒有選擇空間，因為都只能減一次，所以輪流操作，奇數個操作流程先手贏，反之后手贏
正式解答：
正規解答來自
令n為較小的數，m為較大的數，可以發現：
當m%n=0時，先手必勝

當m>=2n時，如果（m%n，m）為必勝態，先手可以先將局勢變為（m%n+n，n），則后手只能將局勢變為（m%n，n）；如果（m%n，n）為必敗態，先手可以直接將局勢變為（m%n，n）。因此，不論（m%n，n）為什么態，先手都必勝

當2n>m>n時，那就是一步一步走下去，直到出現m%n=0||m>=2n結束

代碼：

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main() {int n,m;while(cin>>n>>m){if(n==0&&m==0)break;if(m>n)swap(n,m);int ans=1;//記錄步伐int f=-1;while(n!=0&&m!=0){if(m>n)swap(n,m);if(n/m!=1||m==0){f=ans;break;}ans++;n-=m;}if(f&1)cout<<"Stan wins"<<endl;else cout<<"Ollie wins"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1525 Euclid‘s Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。