a677:
燈泡
Content
我們現在有 N 個完全一樣的電燈泡，及一台最高可以產生 1 至 K 毫安培 ( 電流單位 ) 的電源產生器。該電源產生器只可以產生整數的電流，即只可產生 1, 2, 3, ..., K 毫安培的電流。我們想知道這些燈泡最大可以承受多大的電流，因此我們要進行一些測試。
測試的方法是首先將電源產生器調至某一個值，然後接上燈泡，這時燈泡有兩個可能性：一是燒掉，另一是發亮但不燒掉。燒掉的燈泡不可以再用，未燒掉的燈泡可以取下再進行下一次實驗。可以假設每個燈泡可以多次使用，其質量都能保持不變。
由於這樣的測試法有一定的危險性，所以我們希望以最少的次數來找出可肯定的答案。所謂肯定的答案，就是指我們確實知道以下三種情況的其中之一：
- 確實知道燈泡可以承受的最大電流是多少毫安培
- 知道燈泡連 1 毫安培都受不了
- 知道燈泡可以承受大於 K 毫安培的電流
例如若我們只有一個燈泡的話，那唯一可行的方法就是把電源調較至 1 毫安培，然後每次增加 1 毫安培地進行測試，直至燈泡燒掉為止。這個方法在最差的情況是要試 K 次。
Input
輸入只有一行數據。
這行數據上有兩個整數 N, K，代表燈泡的個數及電流產生器可以產生的最大電流。( 1 <= N <= 20, 2 <= K <= 1200 )
Output
輸出資料只含有一個整數，它代表你所找到的答案，即在最差的情況下可以肯定找到可承受的測試次數。
Sample Input
#1
2 3
Sample Output
#1
2
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
Hint ：
上例代表我們有兩個燈泡，而電流產生器最高可以產生 3 毫安培的電流。這個情況下，我們最多要測試 2 次就可以肯定燈泡可以承受的最大電流。其方法如下：首先將電流產生器調到 2 毫安培，測試燈泡，這時有兩個可能：
- 若燈泡燒掉了，則把電流產生器調至 1 毫安培再試一個新燈泡，這時，無論燈泡燒掉與否我們都可以得到一個肯定的答案。
- 若燈泡沒燒掉，則把電流產生器調至 3 毫安培再試，這時無論燈泡燒掉與否我們都可以得到一個肯定的答案。
由上面的分析，我們可以知道無論如何我們最多只有測試兩次就可以得到一個肯定的答案。
#非官方測試數據
Tags:
出處:
MOI 2018
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||