Cod sursa(job #254538)

Utilizator raduzerRadu Zernoveanu raduzer Data 7 februarie 2009 12:48:40
Problema Planeta Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 0.8 kb
#include <cstdio>

const int MAX_N = 35;

int n, k, s, z;
int 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 + d[i - 1] * d[l - i] * z >= k) break;
		q += 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 %d", &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]);
}