Cod sursa(job #258072)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 14 februarie 2009 16:57:28
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>

#define MAXN 35
#define ll long long

int N, L;
int S[MAXN];
ll K;
ll C[MAXN];

void reconstruct(int p, int r, ll K)
{
	int i;

	for (i = p; i <= r && C[i-p]*C[r-i] <= K; i++) K -= C[i-p] * C[r-i];

	S[++L] = i;

    if (p <= i-1) reconstruct(p, i-1, K / C[r-i]);
    if (i+1 <= r) reconstruct(i+1, r, K % C[r-i]);
}

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

	int i, j;

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

	C[0] = 1;

	for (i = 1; i <= N; i++)
		for (j = 1; j <= i; j++) C[i] += C[j-1] * C[i-j];

	reconstruct(1, N, K-1);

	for (i = 1; i <= N; i++) printf("%d ", S[i]);
	printf("\n");

	return 0;
}