eolymp
bolt
Try our new interface for solving problems
Problems

Constructing BST

Constructing BST

\textbf{BST} (Binary Search Tree) is an efficient data structure for searching. In a \textbf{BST} all the elements of the left sub-tree are smaller and those of right sub-tree are greater than the root. A typical example of \textbf{BST} is -- \includegraphics{https://static.e-olymp.com/content/51/510c70a9cd632c02963b5d218e9ce6c5af6fa98c.jpg} Normally, we construct \textbf{BST} by successively inserting an element. In that case, the ordering of elements has great impact on the structure of the tree. Look at the following cases: \includegraphics{https://static.e-olymp.com/content/bb/bbd0a4f736f0f05cdd755cac2cc3981fc1042ef3.jpg} In this problem, you have to find the order of \textbf{1 }to \textbf{n} integers such that the \textbf{BST} constructed by them has height of at most \textbf{h}. The height of a \textbf{BST} is defined by the following relation: \begin{enumerate} \item \textbf{BST} having no node has height \textbf{0}. \item Otherwise, it equals to \textbf{1} plus maximum of the height of the left sub-tree and right sub-tree. \end{enumerate} Again, several orderings can satisfy the criterion. In that case we prefer the sequence where smaller numbers come first. For example, for \textbf{n = 4}, \textbf{h = 3} we want the sequence \textbf{1 3 2 4} rather than \textbf{2 1 4 3} or \textbf{3 2 1 4}. \InputFile Each test case contains two positive integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000}) and \textbf{h} (\textbf{1} ≤ \textbf{h} ≤ \textbf{30}). Input is terminated by \textbf{n = 0}, \textbf{h = 0}. This case should not be processed. There can be at most \textbf{30} test cases. \OutputFile Output of each test case should consist of a line starting with "\textbf{Case #: }" where "\textbf{#}" is the test case number. It should be followed by the sequence of \textbf{n} integers in the same line. There must not be any trailing space at the end of the line. If it is not possible to construct such tree then print "\textbf{Impossible.}" (without the quotes).
Time limit 1 second
Memory limit 128 MiB
Input example #1
4 3
4 1
6 3
0 0
Output example #1
Case 1: 1 3 2 4
Case 2: Impossible.
Case 3: 3 1 2 5 4 6