Cod sursa(job #257435)

Utilizator CezarMocanCezar Mocan CezarMocan Data 13 februarie 2009 12:28:39
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>

using namespace std;

int n, i, j;
long long k, a[32];

void baga(int left, int right, long long k) {
	int nod;
	long long s, sc;
	
	if (left > right)
		return;
	
	if (left == right) {
		printf("%d ", left);
		return;
	}
	
	s = 0;
	for (nod = left; nod <= right; nod++) {
		s += a[nod - left] * a[right - nod];
		if (s >= k) {
			sc = s - a[nod - left] * a[right - nod];
			k -= sc;
			//nod--;
			fprintf(stderr, "%d %d %lld %d\n", left, right, k, nod);
			printf("%d ", nod);
			baga(left, nod - 1, (k - 1) / a[right - nod] + 1);
			baga(nod + 1, right, (k - 1) % a[right - nod] + 1);
			return;
		}
	}
	
}

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