在一個遊戲中，X 先取 1 個石子，然後 Y 取 2 個石子，接著 X 取 3 個石子，以此類推，找出獲勝者。

---

有兩個玩家 X 和 Y，他們正在玩一個遊戲。X 先開始，可以從無限數量的石子中取走 1 個石子；然後 Y 取 2 個石子；接著 X 取 3 個石子，以此類推，遊戲輪流進行，直到 X 取走的石子總數小於等於給定數字 A，或者 Y 取走的石子總數小於等於另一個給定數字 B。如果任何玩家當前的石子總數超過該玩家的給定最大值，則該玩家不能再取石子，並輸掉遊戲。

輸入

int a = 7 , b = 6; 

輸出

Y is the winner 

解釋：X 先取走 1 個石子，然後 Y 取走 2 個石子，X 再取走 3 個石子，Y 取走 4 個石子。

X 的石子數量為 4，如果他再取 5 個，就會超過 7，所以 Y 獲勝。

方法一

在這個方法中，我們將遍歷 while 迴圈，並將當前數量的石子新增到 x 和 y 中。

示例

#include <bits/stdc++.h>
using namespace std;

// function to find the answer 
int findWinner(int a, int b){
	// creating variables to store the current number of stones for both the player's 
	int sumX = 0, sumY = 0;
	int current = 1; // variable to store the current count of stones 
	// traversing over the loop 
	while (sumX <= a && sumY <= b){
		if(current & 1){
		   // x will always get the odd number of stones
		   sumX += current;
		} else{
		   sumY += current; // y will always get the even number of stones 
		}
	   current = current + 1; // increasing the current value 
	}
	if(sumX > a){
	   return 2; // indicating 2 (Y) is winner 
	} else{
	   return 1; // indicating 1 (X) is winner 
	}
}
int main(){
	int a = 7, b = 5; // given upper limits 
	// calling the function 
	if(findWinner(a,b) == 1){
	   cout<<"X is the winner of the game"<<endl;
	} else{
	   cout<<"Y is the winner of the game"<<endl; 
	}
	return 0;
}

輸出

X is the winner of the game

時間和空間複雜度

上述程式碼的時間複雜度為 O(sqrt(min(A, B)))，其中 A 和 B 是給定的步數。在這裡，我們在每一步都增加計數，加法帶來了平方根的因素。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

方法二

在這個方法中，我們將遍歷 for 迴圈，並將當前數量的石子新增到 x 和 y 中。

示例

#include <bits/stdc++.h>
using namespace std;

// function to find the answer 
int findWinner(int a, int b){
	// creating variables to store the current number 
	// of stones for both the players 
	int sumX = 0, sumY = 0;
	// traversing over the loop 
	for(int i=1; sumX <= a && sumY <=b; i++){
		if(i & 1){
		   sumX += i;
		} else{
		   sumY += i; 
		}
	}
	if(sumX > a){
	   return 2; // indicating 2 (Y) is winner 
	} else{
	   return 1; // indicating 1 (X) is winner 
	}
}
int main(){
	int a = 7, b = 6; // given upper limits 
	// calling the function 
	if(findWinner(a,b) == 1){
	   cout<<"X is the winner of the game"<<endl;
	} else{
	   cout<<"Y is the winner of the game"<<endl; 
	}
	return 0;
}

輸出

Y is the winner of the game

時間和空間複雜度

上述程式碼的時間複雜度為 O(sqrt(min(A, B)))，因為我們只是將迴圈方法從之前的程式碼更改了。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

方法三

在這個方法中，我們將使用數學公式來獲得 x 和 y 的最大可能值，然後進行比較。

示例

#include <bits/stdc++.h>
using namespace std;

int findWinner(int a, int b){
	// creating variables to store the current number of stones for both the players 
	int sumX = 0, sumY = 0;
   int maxA = sqrt(a);
   int maxB = (sqrt(4 * b + 1) - 1)/2;
   if(maxA*maxA == a){
      maxA++;
   }
   if((maxB * (maxB + 1)) == b){
      maxB++;
   }
	if(maxA <= maxB){
	   return 2; // indicating 2 (Y) is winner 
	} else{
	   return 1; // indicating 1 (X) is winner 
	}
}
int main(){
	int a = 7, b = 6; // given upper limits 
	if(findWinner(a,b) == 1){
	   cout<<"X is the winner of the game"<<endl;
	} else{
	   cout<<"Y is the winner of the game"<<endl; 
	}
	return 0;
}

輸出

Y is the winner of the game

時間和空間複雜度

上述程式碼的時間複雜度為 O(log(A + B))，因為我們使用了在對數時間內工作的 sqrt 方法。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

結論

在本教程中，我們實現了三種不同的方法來找出兩個玩家之間的獲勝者，他們玩的遊戲是第一個人取奇數個石子，另一個人取連續的偶數個石子，直到給定數字 A 和 B 的最大總和。第一個無法取石子的玩家將輸掉遊戲。