e-olymp
Задачи

Создание двоичного дерева поиска

Создание двоичного дерева поиска

БДП (бинарное дерево поиска) является эффективной структурой для поиска. В БДП все элементы левого поддерева меньше, а все элементы правого поддерева больше чем значение корня. Рассмотрим пример БДП:

prb1516

Обычно БДП строится в результате последовательной вставки элементов. В таком случае последовательность вставки элементов влияет на структуру результирующего дерева. Например:

prb1516-1

В этой задаче Вам необходимо найти такой порядок вставки чисел от 1 до n, чтобы полученное БДП имело высоту не больше h. Высота БДП определяется следующим образом:

  1. Высота БДП, которое не содержит ни одной вершины, равна 0.
  2. Иначе высота БДП равна 1 плюс максимум высот левого и правого поддерева.

Условию задачи могут удовлетворять несколько последовательностей вставок. В таком случае следует вывести последовательность, в которой сначала идут меньшие числа. Например, для n = 4, h = 3 следует вывести последоватлеьность 1 3 2 4, а не 2 1 4 3 или 3 2 1 4.

Входные данные

Каждый тест содержит два натуральных числа n (1n10000) и h (1h30). Последний тест содержит n = 0, h = 0 и не обрабатывается. На вход подается не более 30 тестов.

Выходные данные

Результат каждого теста следует вывести в отдельной строке. Каждая строка начинается с "Case #: ", где "#" - номер теста. Дальше в этой же строке следует вывести последовательность из n целых чисел – порядок вершин, в котором они будут вставляться в БДП высоты не более h. В конце строки не должно быть пробелов. Если требуемое дерево построить нельзя, то вывести "Impossible." (без кавычек).

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
4 3
4 1
6 3
0 0
Выходные данные
Case 1: 1 3 2 4
Case 2: Impossible.
Case 3: 3 1 2 5 4 6