Cod sursa(job #2749855)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 8 mai 2021 16:22:54
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("planeta.in");
ofstream fout("planeta.out");

struct nod
{
    int val;
    nod *stanga, *dreapta;

};

int n;
long long k,ct;

void Preorder(nod * radacina)
{
    if(radacina!=nullptr)
    {
        fout<<radacina->val<<" ";
        Preorder(radacina->stanga);
        Preorder(radacina->dreapta);

    }
}


vector <nod*> allBST(int stanga, int dreapta)
{
    //construiesc recursiv toti BST


        vector <nod*> bucati;
        if(stanga > dreapta)
            bucati.push_back(nullptr);

        else
        {
            //vor fi in ordine lexicografica pentru ca valorile se iau de la mic la mare
            for(int i=stanga; i<=dreapta && ct<k; ++i) //iau fiecare nod pe rand si-l consider radacina
            {
                vector <nod*> subStanga=allBST(stanga,i-1);
                vector <nod*> subDreapta=allBST(i+1,dreapta);

                //conectez radacina cu subarborele stang si cu cel drept
                for(int j=0; j<subStanga.size() && ct<k ; ++j)
                    for(int z=0; z<subDreapta.size() && ct<k ; ++z)
                    {
                        nod* radacina=new nod();
                        radacina->val=i;
                        radacina->stanga=subStanga[j];
                        radacina->dreapta=subDreapta[z];

                        if(dreapta-stanga+1==n) //adaug radacina unui intreg BST cu n noduri
                        {
                            ct++;
                            if(ct==k) // preordinea nr k
                                bucati.push_back(radacina);

                        }
                        else
                            bucati.push_back(radacina);


                    }

            }

        }

        return bucati;



}
void allBstPreorders()
{

    vector <nod*> radacini=allBST(1,n);
    Preorder(radacini[0]); //am pus doar preordinea nr k

}

int main()
{

    fin>>n>>k;
    allBstPreorders();

    return 0;
}