10821 - Constructing BST

Problem B
Constructing BST
Input: Standard Input

Output: Standard Output

BST (二元搜尋樹)是一個在搜索上有效率的資料資料結構。在 BST 中，左子樹的元素值全小於根節點，而右子樹元素值全大於根節點。一個典型的 BST 如上圖。

一般來說，我們建立一棵 BST 連續地插入一個元素，在這樣的情況看來，插入的順序將會影響樹的結構。可以看到下面的例子：

在這個問題中，你必須找到一個順序，插入範圍 1 到 N 的整數，建造出來的 BST 高度最多為 H，BST 的高度定義如下：

1.      BST 若沒有節點，高度定為 0

2.     此外，高度將由左右子樹的最大高度加 1

但會有一些順序符合條件，這裡我們希望輸出序列順序越小越好(字典順序最小) 。

例如：N = 4, H = 3, 只需輸出 1 3 2 4，而非 2 1 4 3 或 3 2 1 4。

Input

每組測資 將會有兩個正整數 N(1≤N≤10000) 和 H (1≤H≤30)。

程序將會於 N = 0, H = 0 停止。 

最多只會有 30 筆輸入。

Output

對於每組輸出一行，開始為“Case #: “ # 表示為第幾筆測資。接著會有 N 個整數序列於同一行。不應輸出多餘的空白於每行尾。如果不可能建造一個 BST，則輸出“Impossible.”。

Sample Input                               Output for Sample Input

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

---

Problem setter: Md. Kamruzzaman

Special Thanks: Syed Monowar Hossain