POJ 1757 - Binary Search

http://poj.org/problem?id=1757

概要

問題文で与えられているコードで，長さ N の配列に対して二分探索を行う．

このコードの出力が「ターゲットは L 回の反復の後，i 番目にありました」というようなメッセージだったとき，ありうる N の値の範囲を答える．

制約

• 0 <= i < 10^4
• 1 <= L <= 14
• 答えの N は 1 <= N <= 10^4

解法

答えは 10^4 通りしかないので，与えられたコードをコピペして N 回実際に二分探索し，目的の L 回で終了するかどうかをチェックするだけ．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int BinarySearch(int x, int N)
 5 {
 6   int p, q, i, L;
 7 
 8   p = 0;
 9   q = N-1;
10   L = 0;
11   while (p <= q) {
12     i = (p + q) / 2;
13     ++L;
14     if (i == x) {
15       return L;
16     }
17     if (x < i)
18       q = i - 1;
19     else
20       p = i + 1;
21   }
22   throw "err";
23 }
24 
25 int main()
26 {
27   int I, L;
28   cin >> I >> L;
29   static int ok[10010];
30   for (int n = I+1; n <= 10000; n++) {
31     int l = BinarySearch(I, n);
32     ok[n] = (l == L);
33   }
34   int cnt = 0;
35   for (int n = I+1; n <= 10000; n++) {
36     if (ok[n] && !ok[n+1]) {
37       ++cnt;
38     }
39   }
40   cout << cnt << endl;
41   for (int n = I+1; n <= 10000; n++) {
42     if (!ok[n-1] && ok[n]) {
43       cout << n;
44     }
45     if (ok[n] && !ok[n+1]) {
46       cout << " " << n << endl;
47     }
48   }
49   return 0;
50 }