a095 - 麥哲倫的陰謀

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個猜帽子遊戲，N 個犯人戴著紅或白帽子，其中 M 頂是紅色的。犯人不知道自己帽子的顏色，也不能交流。他們需要確定自己帽子的顏色才能出獄。題目要求計算最少需要幾天，所有犯人都能確定自己帽子的顏色。

解題思路

這道題的核心在於理解犯人的推理過程。如果只有一頂紅帽子，戴紅帽子的人在第一天就能確定自己是紅帽子，因為他看到其他人都戴白帽子。如果有多頂紅帽子，情況會更複雜。

關鍵的觀察是，如果一個犯人看到 M-1 頂紅帽子，他就能確定自己戴的是紅帽子。因為如果他戴的是白帽子，那麼其他人看到的紅帽子數量就會是 M 頂，那麼他們中的任何一個戴紅帽子的人在第一天就能確定自己是紅帽子。

因此，如果 M=1，答案是 1。如果 M=2，戴紅帽子的人會等待第二天，因為他們看到至少一頂紅帽子。第二天，如果還沒有人宣布自己是紅帽子，他們就能確定自己是紅帽子。以此類推，如果 M=N，則需要 N 天。

題目中給定的條件是 M > N 時輸出 N+1，否則輸出 N。這實際上是基於上述推理的簡化結果。當 M > N 時，意味著紅帽子數量超過了犯人總數，這是不可能的，題目條件有誤。但根據題目範例，當 M > N 時，輸出 N+1。

複雜度分析

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

程式碼

#include <iostream>

using namespace std;

int main(){
	long long int M,N;
	while(cin >> M >> N){
		if(M>N){
			cout << N+1 << endl; 
		}
		else{
			cout << N << endl;
		}
		
	}
	
}