1358 . 丟失的數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

100.0% (19/19)

Submission's AC Ratio

76.7% (23/30)

Tags

CKsum 2008-CKsum-1st

Description

現在有 $n-1$ 個數（$a_1, a_2, \dots, a_{n - 1}$），範圍是 $0 \sim n-1$，兩兩不相同。請問 $0 \sim n-1$ 中沒有出現在這 $n-1$ 個數的是哪一個數字？每次可詢問第 $i$ 個數二進位表示法的右邊數來第 $j$ 位（$B_{i, j}$），請用儘量少次的詢問找出答案。

Input Format

本題有多組測試資料

每筆測試資料含有一行一個數字，代表題目中的 $n (1 \le n \le 10 ^ 9)$

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