Cod sursa(job #254713)

Utilizator ScrazyRobert Szasz Scrazy Data 7 februarie 2009 13:50:56
Problema Planeta Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.03 kb
#include <cstdio>

long long n, k;
long long dp[31][31];
long long all[31];
int res[31];
int viz[31];

int main()
{
	freopen("planeta.in","r",stdin);
	freopen("planeta.out","w",stdout);
	scanf("%lld%lld", &n, &k);
	all[0] = all[1] = 1;
	dp[1][1] = 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= i; ++j)
			dp[i][j] = all[i - (i - j + 1)] * all[i - j];
		all[i] = 0;
		for (int j = 1; j <= i; ++j)
			all[i] += dp[i][j];
	}
	//printf("%lld", all[n]);
	
	long long sum;
	viz[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		sum = 0;
		int j, l;
		for (j = 0; sum <= k && j <= n; sum += dp[n - i + 1][j]) ++j;
		sum -= dp[n - i + 1][j]; --j;

		if (sum < k)
		{
			++j;
			sum += dp[n - i + 1][j];
			for (l = j; l <= n && viz[l]; ++l);
			res[i] = l;
			viz[l] = 1;
			k = sum - k;
		}
		else
		{
			for (l = j; l <= n && viz[l]; ++l);
			res[i] = l;
			viz[l] = 1;
			for (l = n; l > 0; --l)
				if (!viz[l]) res[++i] = l;
		}
		
	}

	for (int i = 1; i <= n; ++i)
		printf("%d ", res[i]);
}