문제1687--Binary Search

### 1687: Binary Search

실행시간 제한: 1 Sec  메모리사용 제한: 18 MB
제출: 39  통과: 18
[제출] [채점기록] [묻고답하기]

#### 문제 설명

The program fragment below performs binary search of an integer number in an array that is sorted in a nondescending order:

 Pascal (file "sproc.pas") const MAXN = 10000; var A: array[0..MAXN-1] of integer; N: integer; procedure BinarySearch(x: integer); var p, q, i, L: integer; begin p := 0; { Left border of the search } q := N-1; { Right border of the search } L := 0; { Comparison counter } while p <= q do begin i := (p + q) div 2; inc(L); if A[i] = x then begin writeln('Found item i = ', i, ' in L = ', L, ' comparisons'); exit end; if x < A[i] then q := i - 1 else p := i + 1 end end; C (file "sproc.c") #define MAXN 10000 int A[MAXN]; int N; void BinarySearch(int x) { int p, q, i, L; p = 0; /* Left border of the search */ q = N-1; /* Right border 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; } }

Before BinarySearch was called, N was set to some integer number from 1 to 10000 inclusive and array A was filled with a nondescending integer sequence.

It is known that the procedure has terminated with the message "Found item i = XXX in L = XXX comparisons" with some known values of i and L.

Your task is to write a program that finds all possible values of N that could lead to such message. However, the number of possible values of N can be quite big. Thus, you are asked to group all consecutive Ns into intervals and write down only first and last value in each interval.

#### 입력 설명

The input file consists of a single line with two integers i and L (0 <= i < 10000 and 1 <= L <= 14), separated by a space.

#### 출력 설명

On the first line of the output file write the single integer number K representing the total number of intervals for possible values of N. Then K lines shall follow listing those intervals in an ascending order. Each line shall contain two integers Ai and Bi (Ai <= Bi) separated by a space, representing first and last value of the interval.

If there are no possible values of N exist, then the output file shall contain the single 0.

#### 입력 예시 Copy

10 3

#### 출력 예시 Copy

4
12 12
17 18
29 30
87 94