Problem A. 歐幾里德的游戲
時間限制 1000 ms
記憶體限制 128 MB
題目描述
歐幾里德的兩個后代Stan和Ollie正在玩一種數字游戲，這個游戲是他們的祖先歐幾里德發明的，給定兩個正整數M和N，從Stan開始，從其中較大的一個數，減去較小的數的正整數倍，當然，得到的數不能小于0，然后是Ollie，對剛才得到的數，和M，N中較小的那個數，再進行同樣的操作……直到一個人得到了0，他就取得了勝利，下面是他們用(25，7)兩個數游戲的程序：
Start：25 7
Stan：11 7
Ollie：4 7
Stan：4 3
Ollie：1 3
Stan：1 0
Stan贏得了游戲的勝利，
現在，假設他們完美地操作，誰會取得勝利呢？
輸入資料
第一行為測驗資料的組數 CC ，下面有 CC 行，每行為一組資料，包含兩個正整數 M,NM,N ， （M,N（M,N 不超過長整型，）
輸出資料
對每組輸入資料輸出一行，如果Stan勝利，則輸出“Stan wins”；否則輸出“Ollie wins”
樣例輸入
2
25 7
24 15
樣例輸出
Stan wins
Ollie wins思路：
決議：因為每次都是最優化操作，顯然當一個人可以有兩種選擇時，顯然，如果奇數倍不贏，偶數倍必贏 即當maxNum/minNum>=2時，那個人必贏，
當一個人只有一次選擇時,即m/n=1時，他只能操作，但并不能確定輸贏，這時候可以判斷什么時候maxNum%minNum=0 eg，7/1 那么他的對手必輸，即他必贏
AC代碼：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<math.h>
using namespace std;
void output(bool flag)
{
if(flag)
cout<<"Stan wins"<<endl;
else
cout<<"Ollie wins"<<endl;
}
//決議：因為每次都是最優化操作，顯然當一個人可以有兩種選擇時，顯然，如果奇數倍不贏，偶數倍必贏 即當maxNum/minNum>=2時，那個人必贏，
//當一個人只有一次選擇時,即m/n=1時，他只能操作，但并不能確定輸贏，這時候可以判斷什么時候maxNum%minNum=0 即 7/1 那么他的對手必輸，即他必贏
bool solve(long long maxNum,long long minNum,long long time)
{
if(maxNum%minNum==0||maxNum/minNum>=2)
return time&1? false :true;//time odd ollie win 偶數 stan win
return solve(minNum,maxNum%minNum,time+1);
}
int main()
{
ios::sync_with_stdio(false);
int c;
cin>>c;
long long m,n;
while(c--)
{
cin>>m>>n;
output(solve(max(m,n),min(m,n),0));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/196255.html
標籤：其他