ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1064. Binary Search

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
The program fragment below performs binary search of an integer number in an array that is sorted in a nondescending order:
Pascal C
```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;
```
```#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", 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 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 shall contain the single 0.

### Примеры

исходные данныерезультат
```9000 2
```
```0
```
```10 3
```
```4
12 12
17 18
29 30
87 94
```
Источник задачи: 2000-2001 ACM Northeastern European Regional Programming Contest
Метки: нет