Algorithm 版 (精华区)

发信人: fobcaesar (温泉企鹅)〓(欢喜的慈雨), 信区: Algorithm
标  题: 1062K-Trees Made to Order-ZJU
发信站: 哈工大紫丁香 (2002年10月17日21:47:38 星期四), 站内信件

2002-10-17 21:40:40
 00:00.00 380K 

#include <stdio.h>

long d[19], s[19];

void printtree(long p, long m)
{
    char i;
    long r;

    for (i = 0, r = d[0] * d[p - 1]; i < p && m > r; i++, r += d[i] * d[p -
 i - 1]);
    r = d[i] * d[p - i - 1] + m - r + d[p - i - 1] - 1;
    if (i)
    {
        printf("(");
        printtree(i, r / d[p - i - 1]);
        printf(")");
    }
    printf("X");
    if (p - i - 1)
    {
        printf("(");
        printtree(p - i - 1, r % d[p - i - 1] + 1);
        printf(")");
    }
}

int main(void)
{
    long i, j, t, n, m, p;

    d[0] = 1;
    s[0] = 0;
    for (i = 1; i < 19; i++)
    {
        t = 0;
        for (j = 0; j < i; j++)
            t += d[j] * d[i - j - 1];
        d[i] = t;
        s[i] = s[i - 1] + d[i];
    }
    while (scanf("%d", &n) != EOF)
    {
        if (n == 0)
        {
            break;
        }
        for (p = 0; p < 19 && n > s[p]; p++);
        m = n - s[p - 1];
        printtree(p, m);
        printf("\n");
    }
    return 0;
}
--
生活就好象被人强奸一样，如果你无力反抗，就只能闭上眼睛享受!
                                                      ——民工大汉零零发

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.103]