Cod sursa(job #311930)

Utilizator tvladTataranu Vlad tvlad Data 4 mai 2009 19:09:50
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#define NO_ASSERT
#ifndef NO_ASSERT
#include <cassert>
#else
inline void assert(bool) {}
#endif

const int N = 31;

int n;
long long m;
long long d[N][N];
long long p[N];

void precalc() {
	p[0] = 1;
	d[1][1] = 1;
	p[1] = 1;
	d[2][1] = 1;
	d[2][2] = 1;
	p[2] = 2;
	for (int t = 3; t <= n; ++t) {
		p[t] = 2*p[t-1];
		d[t][1] = d[t][t] = p[t-1];
		for (int k = 2; k <= t-1; ++k) {
			d[t][k] = p[k-1]*p[t-k];
			p[t] += d[t][k];
		}
	}
}

void print ( int n, long long m, int offset ) {
	if (n == 1) {
		assert(m == 1);
		printf("%d ",1+offset);
		return;
	}
	long long s = 0;
	int x;
	for (x = 1; x <= n && m > s; ++x) {
		s += d[n][x];
	}
	assert(m <= s);
	--x;
	s -= d[n][x];
	assert(m > s);
	m -= s;
	printf("%d ",x+offset);
	if (x == n) {
		print(n-1,m,offset);
	} else
	if (x == 1) {
		print(n-1,m,offset+1);
	} else {
		if (m % p[n-x] == 0) {
			print(x-1,m/p[n-x],offset);
			print(n-x,p[n-x],offset+x);
		} else {
			print(x-1,m/p[n-x]+1,offset);
			print(n-x,m%p[n-x],offset+x);
		}
	}
}

int main() {
	freopen("planeta.in","rt",stdin);
	freopen("planeta.out","wt",stdout);
	scanf("%d %lld",&n,&m);
	precalc();
	print(n,m,0);
	printf("\n");
	return 0;
}