a095: 麥哲倫的陰謀
Tags : 賽局理論 邏輯
Accepted rate : 3110人/3865人 ( 80% ) [非即時]
評分方式:
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
10 1
10 2
Sample Output
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 (參賽證明 +1)
]


ID User Problem Subject Hit Post Date
17576
gary0317 (ChinoCo)
a095
解法介紹
891 2019-04-23 23:57
16119
10555088@mail.h... (3.141592653589793238...)
a095
想法
1625 2018-11-22 22:57