" 猜帽子 "

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

但猜錯者須以死謝罪

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

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

因此

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

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

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

輸入說明

輸入兩數N，M （1 < M <= N < 231）

代表N個犯人，M頂紅帽

輸出說明

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

範例輸入 #1

10 1
10 2

範例輸出 #1

2
3

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (30%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M

提示：

輸入範例第一筆中

代表有10個犯人，1頂紅帽

第一天：

戴紅帽的看到其他人均戴白帽，又紅帽至少一頂，因此他可以肯定自己是紅帽，並告訴邪惡的麥哲倫所長

第二天：

戴白帽的犯人發現眼中唯一戴紅帽的人走了，代表他知道自己絕對不是紅帽，所以戴紅帽的人才敢走，因此第二天大家都可知道自己是白的

>> 第二天大家均可出獄

標籤:

賽局理論邏輯

出處:

2011 TOI 培訓內容 [管理者： kevin830222 (kkshyu) ]