eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

  1. Высота БДП, которое не содержит ни одной вершины, равна 0.

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4 3
4 1
6 3
0 0
Çıxış verilənləri #1
Case 1: 1 3 2 4
Case 2: Impossible.
Case 3: 3 1 2 5 4 6