Cod sursa(job #257663)

Utilizator savimSerban Andrei Stan savim Data 13 februarie 2009 19:08:11
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>

#define LL long long
#define MAX_N 35

LL c[MAX_N][MAX_N][MAX_N], fin[MAX_N], m;

void parc(int n, LL m, int afis) {
	LL cop = m;
	
	if (n == 0) return;
	
	for (int i = 0; i < n; i++)
		if (c[n][i][n - i - 1] <= cop) cop -= c[n][i][n - i - 1];
		else {
			printf("%d ", afis + i);
			
			parc(i, cop / fin[n - i - 1], afis);
			parc(n - i - 1, cop % fin[n - i - 1], afis + i + 1);
			
			break;
		}
}

int main() {

	freopen("planeta.in", "r", stdin);
	freopen("planeta.out", "w", stdout);
	
	int n;
	scanf("%d %lld", &n, &m);
	
	c[1][0][0] = 1;
	fin[0] = fin[1] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 0; j < i; j++) {
			c[i][j][i - j - 1] = 1LL * fin[j] * fin[i - j - 1];
			fin[i] += c[i][j][i - j - 1];
		}
	
	parc(n, m - 1, 1);
	
	return 0;
}