Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2054
Binary Search

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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


  MAXN = 10000;
  A: array[0..MAXN-1] of integer;
  N: integer;

procedure BinarySearch(x: integer);
  p, q, i, L: integer;
  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;
    if A[i] = x then begin
      writeln('Found item i = ', i,
        ' in L = ', L, ' comparisons');
    if x < A[i] then
      q := i - 1
      p := i + 1


#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;
    if (A[i] == x) {
      printf("Found item i = %d"
        " in L = %d comparisons\n", i, L);
    if (x < A[i])
      q = i - 1;
      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 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 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.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input


9000 2

10 3

Sample Output


12 12
17 18
29 30
87 94

Source: Northeastern Europe 2000
Submit    Status