이진 탐색

아래 프로그램 조각은 오름차순(비내림차순)으로 정렬된 배열 A에서 정수 x를 이진 탐색으로 찾는다.

#define MAXN 10000

int A[MAXN];
int N;

void BinarySearch(int x)
{
  int p, q, i, L;

  p = 0;      /* left boundary of the search */
  q = N - 1;  /* right boundary of the search */
  L = 0;      /* comparison counter */
  while (p <= q) {
    i = (p + q) / 2;
    ++L;
    if (A[i] == x) {
      printf("Found item i = %d in L = %d comparisons\n", i, L);
      return;
    }
    if (x < A[i])
      q = i - 1;
    else
      p = i + 1;
  }
}

BinarySearch를 호출하기 전에 N은 $1 \le N \le 10000$ 범위의 어떤 정수로 설정되고, 배열 A에는 비내림차순 정수 수열이 채워져 있다.

이 프로시저가 어떤 특정한 i와 L 값에 대해 Found item i = XXX in L = XXX comparisons 메시지를 출력하며 종료했다는 사실이 알려져 있다.

이러한 메시지가 나올 수 있는 모든 N의 값을 찾는 프로그램을 작성하라. 가능한 N의 개수가 매우 많을 수 있으므로, 연속된 N들을 구간으로 묶어 각 구간의 첫 값과 마지막 값만 출력한다.

공백으로 구분된 두 정수 i와 L($0 \le i < 10000$, $1 \le L \le 14$)이 한 줄에 주어진다.

첫째 줄에 가능한 N 값들의 구간 개수 K를 정수 하나로 출력한다.

이어서 K개의 줄에 각 구간을 오름차순으로 한 줄에 하나씩 출력한다. 각 줄에는 그 구간의 첫 값과 마지막 값을 나타내는 두 정수 A_i와 B_i($A_i \le B_i$)를 공백으로 구분하여 적는다.

가능한 N 값이 하나도 없으면 0 하나만 한 줄에 출력한다.