1358 . 丟失的數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

100.0% (19/19)

Submission's AC Ratio

76.7% (23/30)

Tags

CKsum 2008-CKsum-1st

Description

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

Input Format

本題有多組測試資料

每筆測試資料含有一行一個數字，代表題目中的 n(1≤n≤109)

Output Format

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

Sample Input 1

15
16

Sample Output 1

25
26

Hints

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

Problem Source

原TIOJ1358 / 快樂暑假營第一次練習比賽。Problem Setter：hallogameboy
2024/07/25 Update: Reformatted & added LATEX by FHVirus

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
Submit
Back to Top