凱文是一位很威的魔術師,他最擅長猜數字的魔術,和觀眾們玩殺手遊戲(註:紙牌遊戲)時總是能夠正確地找出殺手,以及猜出殺手手上那張樸克牌的點數。
不過這次,他想要來點不一樣的。
這位魔術師準備了m枚金幣,放在桌上,然後請觀眾選定一個1到n之間的正整數p。
當然,n是魔術師的助手事先設定好的。
魔術師每一次都會花1枚金幣詢問這個觀眾一個問題:「請問你選的數字是否小於等於k?」而觀眾只能回答「是」或者「不是」。此外,如果觀眾所選的數字p大於k,那麼觀眾可以再從桌上拿走1枚金幣,作為魔術師低估數字的懲罰。接著魔術師再繼續問下一個問題,或者做出最終猜測。
萬一在觀眾拿金幣的當下,或是魔術師欲詢問觀眾問題之前,桌子上已經沒有金幣可以拿,又或者魔術師猜錯數字,那麼魔術師的魔術就宣告失敗了!
一枚金幣也拿不回來,而且還會被大家笑。
不過如果觀眾所選的數字被猜中了,魔術師將會得到大家熱烈的掌聲,然後,最重要的是,把金幣通通拿回來,觀眾只能兩手空空地望洋興嘆。
現在,身為這位好威的魔術師凱文得力助手的你,為了獲得最大的魔術效果,但又不能有損失金幣的任何機會,你該如何選擇最大的n使得這個魔術沒有任何失敗的機會呢?
輸入一個正整數m。
請幫魔術師選定不會出差錯的n的最大可能值。
佔總分50%的測試資料中,1<= m<= 40。
對於全部的測試資料而言,1<= m<= 100,000。
原TIOJ1571 / 97建中校內資訊能力競賽(prob2)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |