Problem B
Constructing BST
Input: Standard Input

Output: Standard Output

Normally, we construct 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:

In this problem, you have to find the order of 1 to N integers such that the BST constructed by them has height of at most H. The height of a BST is defined by the following relation –

1.      BST having no node has height 0.

2.      Otherwise, it is equal to the maximum of the height of the left sub-tree and right sub-tree plus 1.

Again, several orderings can satisfy the criterion. In that case we prefer the sequence where smaller numbers come first. For example, for N=4, H=3 we want the sequence 1 3 2 4 rather than 2 1 4 3 or 3 2 1 4.

Input

Each test case starts with two positive integers N(1≤N≤10000) and H (1≤H≤30). Input is terminated by N=0, H=0. This case should not be processed. There can be at most 30 test cases.

Output

Output of each test case should consist of a line starting with “Case #: “where ‘#’ is the test case number. It should be followed by the sequence of 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 “Impossible.” (without the quotes).

Sample Input                               Output for Sample Input

0 0

Problem setter: Md. Kamruzzaman

Special Thanks: Syed Monowar Hossain

題目解法：

BST 的建法跟考試差不多，依序插入 N 個點，而高度最多 H。

但是要輸出字典順序最小，很明顯地一定是前序走訪。

那麼再找根的時候，盡可能讓右子樹的個數越多越好，但高不可以超過 H。

一棵 N 個點的高度，最小也要 log2(N)+1。

那麼使用遞迴去處理！

有可能高度大於點個數，那是徒勞的。直接把高度 H = N

#include <stdio.h>
void dfs(int l, int r, int h) {
    if(l > r)   return;
    int i, root;
    if(r - ((1<<h)-1) >= l)
        root = r - ((1<<h)-1);
    else
        root = l;
    printf(" %d", root);
    if(h == 0)  return;
    dfs(l, root-1, h-1);
    dfs(root+1, r, h-1);
}
int main() {
    int n, h;
    int cases = 0;
    while(scanf("%d %d", &n, &h) == 2 && n) {
        printf("Case %d:", ++cases);
        if((1<<h) <= n) {
            puts(" Impossible.");
            continue;
        }
        if(h >= n)  h = n;
        dfs(1, n, h-1);
        puts("");
    }
    return 0;
}