TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

24.3% (18/74)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10