TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

50.0% (10/20)

Description

凱文是一位很威的魔術師,他最擅長猜數字的魔術,和觀眾們玩殺手遊戲(註:紙牌遊戲)時總是能夠正確地找出殺手,以及猜出殺手手上那張樸克牌的點數。

不過這次,他想要來點不一樣的。
這位魔術師準備了m枚金幣,放在桌上,然後請觀眾選定一個1到n之間的正整數p。
當然,n是魔術師的助手事先設定好的。

魔術師每一次都會花1枚金幣詢問這個觀眾一個問題:「請問你選的數字是否小於等於k?」而觀眾只能回答「是」或者「不是」。此外,如果觀眾所選的數字p大於k,那麼觀眾可以再從桌上拿走1枚金幣,作為魔術師低估數字的懲罰。接著魔術師再繼續問下一個問題,或者做出最終猜測。

萬一在觀眾拿金幣的當下,或是魔術師欲詢問觀眾問題之前,桌子上已經沒有金幣可以拿,又或者魔術師猜錯數字,那麼魔術師的魔術就宣告失敗了!
一枚金幣也拿不回來,而且還會被大家笑。

不過如果觀眾所選的數字被猜中了,魔術師將會得到大家熱烈的掌聲,然後,最重要的是,把金幣通通拿回來,觀眾只能兩手空空地望洋興嘆。

現在,身為這位好威的魔術師凱文得力助手的你,為了獲得最大的魔術效果,但又不能有損失金幣的任何機會,你該如何選擇最大的n使得這個魔術沒有任何失敗的機會呢?

Input Format

輸入一個正整數m。

Output Format

請幫魔術師選定不會出差錯的n的最大可能值。

Sample Input

範例輸入1
2

範例輸入2
11

Sample Output

範例輸出1
2

範例輸出2
144

Hints

佔總分50%的測試資料中,1<= m<= 40。
對於全部的測試資料而言,1<= m<= 100,000。

Problem Source

原TIOJ1571 / 97建中校內資訊能力競賽(prob2)

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144
7 5000 65536 262144
8 5000 65536 262144
9 5000 65536 262144