a095: 麥哲倫的陰謀

內容

在禁忌的貝殼城裡存在著一座監獄

有 N 個犯人被關在裡頭

我們只知道 …..

“他們都帶著帽子”

這是一頂神奇的帽子

稱作 “廬山帽”

是貝殼城裡的特產

分為紅色及白色兩種

凡是帶上 “廬山帽” 的人 ……

就會 “不識廬山真面目” !!!!

而監獄內的所有犯人都被配帶了這一頂可怕的帽子 0.0

而邪惡的所長麥哲倫想到了一個邪惡又沒有良心的鬼計畫：

“ 猜帽子 “

只要能猜出自己的帽子顏色即可立即出獄

但猜錯者須以死謝罪

而你可以假設監獄裡的犯人都跟羅賓一樣絕頂聰明

不會有想要以死謝罪的白痴行為

因此

在 N 個犯人的監獄中，麥哲倫所長將 M 頂紅帽配給其中的犯人

請問最少需要幾天，監獄內的所有犯人均可以確定自己的帽子顏色後出獄

PS. 犯人並不知道共有幾頂紅帽，只知道紅帽至少有一頂，而且不可互相討論 = =

輸入

輸入兩數 N，M （1 < M <= N < 2³¹）

代表 N 個犯人，M 頂紅帽

10 1
10 2

輸出

輸出最少幾天所有犯人均可以確定自己的帽子顏色後出獄

2
3

解題思路

重點在紅帽的數量，白帽不會影響邏輯判斷

1. 如果只有 1 頂，紅帽人看到其他人都是白帽，就能確定自己是紅帽，他就能確定自己是紅帽離開。
   第 2 天白帽人發現戴紅帽人走了，就能確定自己是白帽離開。

2. 如果有 2 頂，紅帽人的只會看到 1 個人戴紅帽(另一個在他頭上)。
   第 2 天，紅帽人發現另一個戴紅帽的不走 = 有人也戴紅帽，但剩下的都是白帽人，所以自己頭上的一定是紅帽，兩個紅帽人的就能確定自己是紅帽離開。
   第 3 天，白帽人發現戴紅帽人走了，就能確定自己是白帽離開。

3. 如果有 3 頂，紅帽人的就會看到 2 個人戴紅帽(最後一個在他頭上)。
   第 2 天，(不重要)
   第 3 天，這時候紅帽人會發現如果自己戴的是白帽，那看到的兩個紅帽人所看到的情況應該是”狀況 2”，但他們第 2 天都沒有離開，代表還有人戴紅帽，但剩下的都是白帽人，所以自己頭上的一定是紅帽，三個紅帽人的就能確定自己是紅帽離開。
   第 4 天，白帽人發現戴紅帽人走了，就能確定自己是白帽離開。

4. 之後情況同理類推。

觀察上面的情況可以發現，紅帽人能確認自己是紅帽並離開的天數是他”看見”的紅帽數 + 1，白帽人能確認自己是白帽並離開的天數是他看見紅帽人離開的天數 + 1，而紅帽人”看見”的紅帽數 + 1 = 紅帽的總數(看不到自己頭上的)，所以可以得到結論：

紅帽人離開天數 = 紅帽數
全部離開天數 = 白帽人離開天數 = 紅帽人離開天數 + 1 = 紅帽數 + 1

唯一要注意的是：如果紅帽數 = 總人數，就不會有白帽人，也就是紅帽人 = 總人數，這時候

全部離開天數 = 紅帽人離開天數 = 紅帽數

完整程式碼

AC (34ms, 100KB)

#include <stdio.h>

int n, m;

int main()
{
    while (scanf(" %d %d", &n, &m) == 2)
    {
        printf("%d\n", n == m ? m : m + 1);
    }
    return 0;
}