e587 - 10530 - Guessing Game

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個猜數字遊戲，Ollie 猜數字，Stan 回應猜測是太高、太低還是正確。Ollie 懷疑 Stan 作弊，即在猜測過程中更改正確答案。程式需要判斷每場遊戲是否證明 Stan 作弊。如果 Stan 的回答與可能的正確答案範圍不符，則 Stan 作弊。

解題思路

程式使用貪婪策略來縮小可能的答案範圍。它維護一個 max 和 min 變數，分別表示可能的最大和最小答案。對於每個猜測，如果 Stan 回應 "high"，則更新 max 為猜測值減一；如果 Stan 回應 "low"，則更新 min 為猜測值加一。如果 Stan 回應 "right on"，則檢查猜測值是否在 min 和 max 之間。如果在範圍內，則 Stan 可能誠實；否則，Stan 作弊。遊戲結束於猜測為 0 或找到正確答案。

複雜度分析

• 時間複雜度: O(N)，其中 N 是猜測的數量。因為程式需要遍歷所有猜測。
• 空間複雜度: O(1)，程式只使用幾個整數變數和一個字串變數，空間使用不隨輸入大小變化。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	int a=1;
	while(a!=0){
		int max=11,min=0;
		string b;
		while(1){
			cin >> a >> b;
			cin >> b;
			if(a==0)
				break;
			if(b=="high"){
				if(a<max)
					max=a;
			}
			else if(b=="low"){
				if(a>min)
					min=a;
			}
			else{
				(max>a&&a>min)?cout << "Stan may be honest\n":cout << "Stan is dishonest\n";
				break;	
			}
		}
	}
}