Pagini recente » Cod sursa (job #1254946) | Cod sursa (job #2476689) | Cod sursa (job #1218883) | Cod sursa (job #147843) | Cod sursa (job #2899343)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
static const LL N = 2 << 4;
LL catalan[N];
void genCatalan(LL n) {
catalan[0] = 1;
catalan[1] = 1;
for (LL i = 2; i <= n; i++)
for (LL j = 1; j <= i; j++)
catalan[i] = catalan[i] + catalan[j - 1] * catalan[i - j];
}
void create(LL left, LL right, LL k) {
if (left > right)
return;
LL i;
for (i = left; i <= right && catalan[i - left] * catalan[right - i] <= k; i++)
k -= (catalan[i - left] * catalan[right - i]);
fout << i << " ";
if (i > left)
create(left, i - 1, k / catalan[right - i]);
if (i < right)
create(i + 1, right, k % catalan[right -i]);
}
int main() {
// CATALAN(N) = (2N)! / ((N+1)! * (N!))
LL n, k;
fin >> n >> k;
genCatalan(n);
create(1, n, k - 1);
return 0;
}