TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

81.8% (18/22)

Description

現在有n-1個數(a1, a2, …, an-1),範圍是0 ~ n-1,兩兩不相同。請問0 ~ n-1中沒有出現在這n-1個數的是哪一個數字?每次可詢問第i個數二進位表示法的右邊數來第j位(Bi,j),請用儘量少次的詢問找出答案。

Input Format

本題有多組測試資料

每筆測試資料含有一行一個數字,代表題目中的n (1<=n<=1000000000)

Output Format

請對於每筆資料輸出一行一個數字,代表對於這個問題,最少詢問幾次可以找出答案。

Sample Input

15
16

Sample Output

25
26

Hints

※2008/07/10 範例測資修正 by akira。

Problem Source

原TIOJ1358 / 快樂暑假營第一次練習比賽。Problem Setter:hallogameboy

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536