Cod sursa(job #2751955)

Utilizator mirunavrAvram Miruna-Alexandra mirunavr Data 16 mai 2021 08:36:41
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<bits/stdc++.h>

using namespace std;
ifstream f("planeta.in");
ofstream g("planeta.out");
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 0;
    }

    if (nrNoduri== 1) {
        g<< start+ 1 <<" ";
        //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;
}