이진 탐색

면접 대비

시간 제한1초메모리 제한128 MB

요약

정렬된 배열에서 이진 탐색이 정확히 L번의 비교 만에 x를 인덱스 i에서 찾았다고 출력할 수 있는 모든 배열 길이 N을 구한다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

아래 프로그램 조각은 오름차순(비내림차순)으로 정렬된 배열 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 하나만 한 줄에 출력한다.

예제2

예제 1
입력
```
9000 2
```
예상 출력
```
0
```
예제 2
입력
```
10 3
```
예상 출력
```
4
12 12
17 18
29 30
87 94
```