Cod sursa(job #254944)

Utilizator raduzerRadu Zernoveanu raduzer Data 8 februarie 2009 10:21:51
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>

const int MAX_N = 35;

int n, s;
long long z, k;
long long d[MAX_N];
int a[MAX_N];

void solve(int st, int dr)
{
    int i;
    if (st > dr) return;
    int l = dr - st + 1;

    if (st == dr) { a[st] = s; return; }
	
    long long q = 0;
    for (i = 1; i <= l; ++i)
    {
        if (q + (long long)d[i - 1] * d[l - i] * z >= k) break;
        q += (long long)d[i - 1] * d[l - i] * z;
    }
    k -= q;
	
    a[st] = s + i - 1;
	
    z *= d[l - i];
    solve(st + 1, st + i - 1);
    z /= d[l - i];
	
    s += i;
    solve(st + i, dr);
    s -= i;
}

int main()
{
    int i, j;
    freopen("planeta.in", "r", stdin);
    freopen("planeta.out", "w", stdout);
	
    scanf("%d %lld", &n, &k);
	
    d[0] = 1;
    for (i = 1; i <= n; ++i)
        for (j = 0; j < i; ++j) d[i] += d[j] * d[i - j - 1];
	
    s = z = 1;
    solve(1, n);
	
    for (i = 1; i <= n; ++i) printf("%d ", a[i]);
}