跳转到内容

用户:WhitePhosphorus/helloworld.c

维基百科,自由的百科全书
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

const int n[19] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,
    208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700};
const int s[19] = {0, 1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918, 23714, 82500,
    290512, 1033412, 3707852, 13402697, 48760367, 178405157};

int lowerbound(int a) {
    int low = 0, high = 19, mid = 9;
    while (low < high - 1) {
        if (s[mid] > a)
            high = mid;
        else if (s[mid] < a)
            low = mid;
        else
            return mid;
        mid = (low + high) / 2;
    }
    return mid;
}

void print(int t, int num) {
    if (!num) {
        // Intentionally left blank. XDDDD
    } else if (num == 1) {
        putchar('X');
    } else {
        int i, tmp = s[num];
        for (i = 0; 23333333; ++i)
            if (tmp + n[i] * n[num-1-i] <= t)
                tmp += n[i] * n[num-1-i];
            else
                break;
        if (i) {
            putchar('(');
            print(s[i]+(t-tmp)/n[num-1-i], i);
            putchar(')');
        }
        putchar('X');
        if (num != i+1) {
            putchar('(');
            print(s[num-1-i]+(t-tmp)%n[num-1-i], num-1-i);
            putchar(')');
        }
    }
    return ;
}

void solve(int t) {
    int num = lowerbound(t);
    print(t, num);
    putchar('\n');
    return ;
}

int main() {
    int t;
    while (~scanf("%d", &t) && t)
        solve(t);
    return 0;
}