Создание двоичного дерева поиска
Создание двоичного дерева поиска
БДП (бинарное дерево поиска) является эффективной структурой для поиска. В БДП все элементы левого поддерева меньше, а все элементы правого поддерева больше чем значение корня. Рассмотрим пример БДП:
Обычно БДП строится в результате последовательной вставки элементов. В таком случае последовательность вставки элементов влияет на структуру результирующего дерева. Например:
В этой задаче Вам необходимо найти такой порядок вставки чисел от 1 до n, чтобы полученное БДП имело высоту не больше h. Высота БДП определяется следующим образом:
Высота БДП, которое не содержит ни одной вершины, равна 0.
Иначе высота БДП равна 1 плюс максимум высот левого и правого поддерева.
Условию задачи могут удовлетворять несколько последовательностей вставок. В таком случае следует вывести последовательность, в которой сначала идут меньшие числа. Например, для n = 4, h = 3 следует вывести последоватлеьность 1 3 2 4, а не 2 1 4 3 или 3 2 1 4.
Входные данные
Каждый тест содержит два натуральных числа n (1 ≤ n ≤ 10000) и h (1 ≤ h ≤ 30). Последний тест содержит n = 0, h = 0 и не обрабатывается. На вход подается не более 30 тестов.
Выходные данные
Результат каждого теста следует вывести в отдельной строке. Каждая строка начинается с "Case #: ", где "#" - номер теста. Дальше в этой же строке следует вывести последовательность из n целых чисел – порядок вершин, в котором они будут вставляться в БДП высоты не более h. В конце строки не должно быть пробелов. Если требуемое дерево построить нельзя, то вывести "Impossible." (без кавычек).
Пример
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