Pagini recente » Cod sursa (job #177896) | Cod sursa (job #371465) | Cod sursa (job #3152890) | Cod sursa (job #44206) | Cod sursa (job #2751957)
#include<bits/stdc++.h>
using namespace std;
ifstream f("planeta.in");
ofstream g("planeta.out");
long long n,k;
long nrBST[32];
//luam pe rand intre 1 si n nodul drept radafa
// https://www.youtube.com/watch?v=YDf982Lb84o.
void genereazaNumarBST (int numarNoduri) {
int i,predecesor;
// cazul de baza
nrBST[0] = 1;
for (i= 1; i<= numarNoduri; i++) {
for (predecesor= 1; predecesor<= i;predecesor++) {
//nrBST[predecesor - 1]-> subarbore stang
//nrBST[i-predecesor]-> subarbore drept
nrBST[i]+= nrBST[predecesor - 1] * nrBST[i - predecesor];
}
}
}
void gasesteKTravesal (int start, int nrNoduri, long long kTraversal) {
int i;
// nimic in subarborele stang/drept
if (nrNoduri== 0) {
return;
//return 0;
}
if (nrNoduri== 1) {
g<< start+ 1 <<" ";
return;
//return 0;
}
for (i = 1; i<=nrNoduri; i++) {
long long nrPermutariSubarboreStang = nrBST[i - 1];
long long nrPermutariSubarboreDrept= nrBST[nrNoduri- i];
long long nrOfPermutations = nrPermutariSubarboreStang * nrPermutariSubarboreDrept;
if (nrOfPermutations < kTraversal) {
kTraversal -= nrOfPermutations;
} else {
g << start +i <<" ";
// subarbore stang
gasesteKTravesal(start,i - 1,(kTraversal - 1) / nrPermutariSubarboreDrept + 1);
// subarbore drept
gasesteKTravesal(start + i,nrNoduri - i,(kTraversal - 1) % nrPermutariSubarboreDrept + 1);
//return 0;
}
}
}
int main () {
f>>n>>k;
genereazaNumarBST(n);
gasesteKTravesal(0, n, k);
return 0;
}