2013年7月7日 星期日

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