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