Description：石頭剪刀布是常見的猜拳游戲。石頭勝剪刀，剪刀勝布，布勝石頭。如果兩個人出拳一樣，則不分勝負。

一天，小A和小B正好在玩石頭剪刀布。已知他們的出拳都是有規律的，比如：“石頭-布-石頭-剪刀-石頭-布-石頭-剪刀……”，就是以“石頭-布-石頭-剪刀”為周期的。請問，小A和小B比了N輪之后，誰贏了？

Input：

輸入的第一行包含一個整數K，表示K組測試數據。
之后的每組測試數據包含三行。第一行包含三個整數：N，NA，NB，分別表示比了N輪，小A出拳的周期長度，小B出拳的周期長度。第二行包含NA個整數，表示小A出拳的規律，第三行包含NB個整數，表示小B出拳的規律。其中，0表示“石頭”，2表示“剪刀”，5表示“布”。?

對于小數據，0 < K,N,NA,NB <= 10;對于大數據，0 < K,N,NA,NB <= 100;?

Output:

對于每組測試數據，輸出一行。如果小A贏了，輸出A；如果小B贏了，輸出B；如果兩人打平，輸出draw。

Sample Input

2 10 3 4 0 2 5 0 5 0 2 5 3 3 2 0 5 0 2 5

?

?

?

?

?

?

?

?

Sample Output

A draw

?

?

?

Hint：

對于第一組測試數據，猜拳過程為： A：0 2 5 0 2 5 0 2 5 0 B：0 5 0 2 0 5 0 2 0 5 所以A贏了4輪，B贏了2輪，雙方打平4輪，所以A贏了。 對于第二組測試數據，猜拳過程為： A：2 0 5 2 0 B：0 2 5 0 2 所以A贏了2輪，B贏了2輪，雙方打平1輪，所以最終打平了。

?

?

?

?

?

?

?

?

?

思路：假設A出拳的周期長度為na，B出拳的周期長度為nb，對于具體的出拳規律則使用兩個數組arrayA[],arrayB[]來保存。

? ? ? ? ?在第i次出拳時，判斷獲勝方的方法：比較A出arrayA[i%na]、B出 arrayB[i%nb]的贏家，統計n次出拳后A總共贏的次數和B總共贏的次數，然后按要求輸出即可。

優化方法：在以上方法中，總是需要比較n次才能算出贏家，這樣在n比較大時可能存在著周期性的重復比較。如n = 40, na = 3，nb =4時，顯然n從13到36的比較就很多余了，所以考慮優化這些多余的比較——聰明如你，肯定想到可以使用na和nb的最小公倍數來進行優化了吧~

此外，思考具體的計算過程是否是將最小公倍數周期內的比較同不滿足整個周期（第37-40次）的比較相加？（PS：之所以將此項單獨列出，是因為在同學的討論中確實存在這樣的誤解，所以看仔細了哦~）

試想在前12次比較中B先贏4次，然后在5-12次中A、B平局2次、A贏6次，然后再第37-40次B贏4次，A總共贏6次，B總共贏8次，最終B取得勝利？

也許你會大聲的說No！在前36次中A共贏18次，B共贏12次；在全40次的比較中A贏18次，B贏16次，結果是A贏。

下面上代碼：

1 #include<iostream> 2 using namespace std; 3 static int winA; 4 static int winB; 5 //求正整數a和b的最大公約數 6 int divisor(int a, int b){ 7 int n = a>b ? a:b; 8 if(a>b) a = b; 9 else return a; 10 while(n%a !=0){ 11 b = a; 12 a = n%a; 13 n = b; 14 } 15 return a; 16 } 17 18 //求正整數a和b的最小公倍數 19 int multiple(int a, int b){ 20 return a/divisor(a,b)*b; 21 } 22 23 void cmp(int arrayA[],int na, int arrayB[], int nb,const int cal) 24 { 25 for(int i=0; i<cal; i++) 26 { 27 int a = i % na; 28 int b = i % nb; 29 //A贏 30 if((arrayA[a]==0 && arrayB[b]==2)||(arrayA[a]==2 && arrayB[b]==5)||(arrayA[a]==5 && arrayB[b]==0)) 31 { 32 winA++; 33 }else if(arrayA[a] != arrayB[b]) 34 {//B贏 35 winB++; 36 } 37 } 38 } 39 40 int main() 41 { 42 int K, N, NA, NB, cal, i; 43 cin>>K; 44 while(K>0){ 45 winA=0, winB=0; 46 cin>>N>>NA>>NB; 47 int* arrayA = (int *)malloc((NA+1)*sizeof(int)); 48 int* arrayB = (int *)malloc((NB+1)*sizeof(int)); 49 for(i=0; i<NA; i++) 50 { 51 cin>>arrayA[i]; 52 } 53 for(i=0; i<NB; i++) 54 { 55 cin>>arrayB[i]; 56 } 57 //通過最小公約數來實現最少的比較次數 58 cal = multiple(NA,NB); 59 if(N <= cal) 60 cmp(arrayA,NA,arrayB,NB,N); 61 else 62 { 63 cmp(arrayA,NA,arrayB,NB,cal); 64 int mod = N % cal, mul = N / cal; 65 winA *= mul; 66 winB *= mul; 67 if(mod) 68 cmp(arrayA,NB,arrayB,NB,mod); 69 } 70 //輸出計算結果 71 if(winA==winB) 72 cout<<"draw"<<endl; 73 else if(winA>winB) 74 cout<<"A"<<endl; 75 else 76 cout<<"B"<<endl; 77 //別忘了釋放空間 78 free(arrayA); 79 free(arrayB); 80 K--; 81 } 82 return 0; 83 }

?

?

?

?

轉載于:https://www.cnblogs.com/Allie0920/archive/2013/04/05/3001612.html

總結

以上是生活随笔為你收集整理的石头剪刀布 -2013编程之美全国测试赛 每日一练的全部內容，希望文章能夠幫你解決所遇到的問題。

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