d347 - 00847 - A Multiplication Game

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個兩人輪流進行乘法遊戲的場景。初始值為 1，玩家輪流將當前值乘以 2 到 9 之間的整數。目標是成為第一個使當前值大於或等於給定整數 n 的玩家。題目要求判斷 Stan 或 Ollie 誰會獲勝，假設兩人都是最佳策略玩家。

解題思路

由於題目要求找出最佳策略，我們可以預先計算 Stan 和 Ollie 在每次輪換時，可以達到的最大值。Stan 先手，Ollie 後手。Stan 的目標是盡快讓數值大於等於 n，而 Ollie 的目標是阻止 Stan。由於兩人都是最佳策略玩家，Stan 會選擇使數值最大化的乘法，而 Ollie 則會選擇使數值最小化的乘法。

程式碼中，ans[i] 儲存了第 i 輪 Stan 能夠達到的最大值。ans[0] 初始化為 9。然後，透過迴圈計算後續的 Stan 和 Ollie 可能達到的最大值。Stan 的回合乘以 9，Ollie 的回合乘以 2。

在主迴圈中，程式碼遍歷預先計算的 ans 陣列，找到第一個大於或等於輸入 n 的值。如果該值對應的索引 i 是奇數，則 Ollie 獲勝；如果索引 i 是偶數，則 Stan 獲勝。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long int ans[18]={9},n;
int main(){
	for(int i=0;i<17;i+=2){
		ans[i+1]=ans[i]*2;
		ans[i+2]=(ans[i+1])*9;
	}
	while(cin >> n){
		for(int i=0;i<17;++i){
			if(ans[i]>=n){
				if(i%2)
					cout << "Ollie wins.\n";
				else
					cout << "Stan wins.\n";
				break;
			}
		}
	}
}