a095. 麥哲倫的陰謀
Tags : 賽局理論 邏輯
Accepted rate : 7171人/8346人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-06 01:06

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

有N個犯人被關在裡頭

我們只知道 .....

"他們都帶著帽子" 


這是一頂神奇的帽子
 
稱作 "廬山帽"
 
是貝殼城裡的特產

分為紅色及白色兩種 

凡是帶上 "廬山帽" 的人 ......

就會 "不識廬山真面目" !!!!

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

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

" 猜帽子 "

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

但猜錯者須以死謝罪 

 

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

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

因此

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

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

 

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

Input

輸入兩數N,M (1 < M <= N < 231)

代表N個犯人,M頂紅帽 

Output
輸出最少幾天所有犯人均可以確定自己的帽子顏色後出獄
Sample Input #1
10 1
10 2
Sample Output #1
2
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
Hint :
輸入範例第一筆中

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

第一天:

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

第二天:

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

>> 第二天大家均可出獄 
Tags:
賽局理論 邏輯
出處:
2011 TOI 培訓內容 [管理者: kevin830222 (kkshyu) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
32854 jasperlin010 ... (Jasper Lin) a095
2531 2022-11-12 17:46
41666 yp11351016@y ... (707-19王淵筑) a095
206 2024-08-15 23:14
41477 austin970205 ... (204鄭源鈞) a095
c++解答
250 2024-07-30 16:27
41294 suyueh (suyueh) a095
python
201 2024-07-16 15:20
39561 henry0985524 ... (張弘勳) a095 632 2024-03-06 15:41