Pagini recente » Cod sursa (job #1815648) | Cod sursa (job #358183) | Cod sursa (job #2096643) | Cod sursa (job #2001001) | Cod sursa (job #2752324)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
int n;
long long k;
// bst[i] - no of binary search trees with i nodes
long long bst[33];
void generate(){
bst[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
//stanga dreapta
bst[i] += bst[j - 1] * bst[i-j];
}
}
}
void solve(int noNodes, long long k, int start){
if(!noNodes){
// gol
return;
}
if(noNodes == 1){
fout << start + 1 << " ";
return;
}
else{
long long permLeft;
long long permRight;
long long perms;
for(int i = 1; i <= noNodes; i++){
permLeft = bst[i-1];
permRight = bst[noNodes - i];
perms = permRight * permLeft;
if( perms < k){
k -= perms;
}
else{
fout << start + i << " ";
solve( i-1, k / permRight + 1, start);
solve( noNodes - i, k % permRight + 1, start + i);
return;
}
}
}
}
int main(){
fin >> n >> k;
generate();
solve(n, k-1, 0);
//
return 0;
}