a095.
麥哲倫的陰謀
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
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
Hint ：
輸入範例第一筆中
代表有10個犯人，1頂紅帽
第一天：
戴紅帽的看到其他人均戴白帽，又紅帽至少一頂，因此他可以肯定自己是紅帽，並告訴邪惡的麥哲倫所長
第二天：
戴白帽的犯人發現眼中唯一戴紅帽的人走了，代表他知道自己絕對不是紅帽，所以戴紅帽的人才敢走，因此第二天大家都可知道自己是白的
>> 第二天大家均可出獄
出處:
2011 TOI 培訓內容
[管理者：
kevin830222
(kkshyu)
]
| ID | User | Problem | Subject | Hit | Post Date |
| 32854 |
|
a095 | 2531 | 2022-11-12 17:46 | |
| 41666 |
|
a095 | 206 | 2024-08-15 23:14 | |
| 41477 |
|
a095 | 250 | 2024-07-30 16:27 | |
| 41294 | suyueh (suyueh) | a095 | 201 | 2024-07-16 15:20 | |
| 39561 |
|
a095 | 632 | 2024-03-06 15:41 |