Cod sursa(job #2751639)

Utilizator DianaZaharia132nr2Zaharia Diana Cristiana DianaZaharia132nr2 Data 15 mai 2021 14:27:12
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("planeta.in");
ofstream gout("planeta.out");
// am observat ca elementele din arbore trebuie sa fie memorate in vector in preordine(RSD=radacina, stanga, dreapta)
//dupa exemplul dat in cerinta
int nr; //numar control rezultate
vector<int> v;

int estearborebst(int s, int d)
{
    if (s >= d) return 1;  //este bst

  int j;
  for (j = s + 1; j <= d; ++j) //cauta primul element din arbore mai mare decat
        if (v[j] > v[s])         //ce se afla pe pozitia curenta din partea stanga
            break;

  for (int i = j; i <= d; ++i)//verifica daca dupa acel element exista vreun element care sa fie mai mic
  { if (v[i] < v[s])       //decat elementul de pe pozitia curenta din partea stanga
            return 0;   }     //pentru ca asta inseamna ca nu e abst


 return estearborebst(s + 1, j - 1) && estearborebst(j, d);
 // verifica daca fiecare subarbore are structura unui arbore bst(prin recursivitate)
//prima bucata verifica daca tot ce e in partea dreapta a partii din stanga e ok
// a doua bucata verifica daca tot ce e in dreapta partii drepte e ok
}

void arboribst(int n)
{ int x; fin>>x;

    for (int i = 1; i <= n; ++i)
        v.push_back(i);

  do
    {
        if (estearborebst(0, n - 1))
        { ++nr;
        if(nr==x)
        {
            for (int i = 0; i < v.size(); ++i)
               gout<<v[i]<<" ";
           }

        }
    }
        while(next_permutation(v.begin(), v.end()) && nr!=x);


}


int main()
{
    int N;
    fin >> N;
    arboribst(N);
fin.close();
gout.close();

    return 0;
}