eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

\textbf{БДП} (бинарное дерево поиска) является эффективной структурой для поиска. В \textbf{БДП} все элементы левого поддерева меньше, а все элементы правого поддерева больше чем значение корня. Рассмотрим пример \textbf{БДП}: \includegraphics{https://static.e-olymp.com/content/51/510c70a9cd632c02963b5d218e9ce6c5af6fa98c.jpg} Обычно \textbf{БДП} строится в результате последовательной вставки элементов. В таком случае последовательность вставки элементов влияет на структуру результирующего дерева. Например: \includegraphics{https://static.e-olymp.com/content/bb/bbd0a4f736f0f05cdd755cac2cc3981fc1042ef3.jpg} В этой задаче Вам необходимо найти такой порядок вставки чисел от \textbf{1 }до \textbf{n}, чтобы полученное \textbf{БДП} имело высоту не больше \textbf{h}. Высота \textbf{БДП} определяется следующим образом: \begin{enumerate} \item Высота \textbf{БДП}, которое не содержит ни одной вершины, равна \textbf{0}. \item Иначе высота \textbf{БДП }равна \textbf{1} плюс максимум высот левого и правого поддерева. \end{enumerate} Условию задачи могут удовлетворять несколько последовательностей вставок. В таком случае следует вывести последовательность, в которой сначала идут меньшие числа. Например, для \textbf{n = 4}, \textbf{h = 3} следует вывести последоватлеьность \textbf{1 3 2 4}, а не \textbf{2 1 4 3} или \textbf{3 2 1 4}. \InputFile Каждый тест содержит два натуральных числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000}) и \textbf{h} (\textbf{1} ≤ \textbf{h} ≤ \textbf{30}). Последний тест содержит \textbf{n = 0}, \textbf{h = 0} и не обрабатывается. На вход подается не более \textbf{30} тестов. \OutputFile Результат каждого теста следует вывести в отдельной строке. Каждая строка начинается с "\textbf{Case #: }", где "\textbf{#}" - номер теста. Дальше в этой же строке следует вывести последовательность из \textbf{n} целых чисел -- порядок вершин, в котором они будут вставляться в \textbf{БДП} высоты не более \textbf{h}. В конце строки не должно быть пробелов. Если требуемое дерево построить нельзя, то вывести "\textbf{Impossible.}" (без кавычек).
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4 3
4 1
6 3
0 0
Выходные данные #1
Case 1: 1 3 2 4
Case 2: Impossible.
Case 3: 3 1 2 5 4 6