Cod sursa(job #254455)

Utilizator devilkindSavin Tiberiu devilkind Data 7 februarie 2009 12:15:44
Problema Planeta Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 0.94 kb
#include <stdio.h>

#define NMAX 32

long long DIN[NMAX];
long long N, K;

void BST(long long st, long long dr, long long k)
{
    long long S = 0, x, y, k1, k2, i;

    if (st > dr) return;

    if (st == dr) {
            printf("%lld ", st);
            return;
    }

    for (i = st; i <= dr; i++)
    {
            x = DIN[i - st];
            y = DIN[dr - i];
            S = S + x * y;
            if (S > k) break;
    }

    k = k - (S - x * y);
    printf("%lld ", i);
    k1 = k / y;
    k2 = k % y;

    BST(st, i - 1, k1);
    BST(i + 1, dr, k2);
}

int main()
{
        freopen("planeta.in", "r", stdin);
        freopen("planeta.out", "w", stdout);

        long long i, j;

        scanf("%lld %lld ", &N, &K);

        DIN[1] = 1;
        DIN[0] = 1;

        for (i = 2; i <= N; i++)
                for (j = 1; j <= i; j++)
                        DIN[i] = DIN[i] + DIN[j - 1] * DIN[i - j];
        
        BST(1, N, K - 1);
        return 0;
}