Pagini recente » Cod sursa (job #2103739) | Cod sursa (job #453814) | Cod sursa (job #894624) | Cod sursa (job #1944761) | Cod sursa (job #2751642)
#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 <n; ++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;
}