TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

77.8% (21/27)

Tags

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 1

15
16

Sample Output 1

25
26

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1