Pagini recente » Cod sursa (job #1971179) | Cod sursa (job #1800967) | Cod sursa (job #2223339) | Cod sursa (job #2053467) | Cod sursa (job #2751828)
#include <bits/stdc++.h>
using namespace std;
/* https://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
Do following for every node pre[i] starting from first one.
1) Find the first greater value on right side of current node.
Let the index of this node be j. Return true if following
conditions hold. Else return false
(i) All values after the above found greater value are
greater than current node.
(ii) Recursive calls for the subarrays pre[i+1..j-1] and
pre[j+1..n-1] also return true.*/
vector<int> v;
bool preorder( int st, int dr){
if(st >= dr)
return 1;
int i;
for(i = st+1 ; i <= dr; i++){
if (v[i] > v[st])
break;}
for(int j = i; j <= dr; j++){
if(v[j]< v[st])
return 0;}
return preorder(st+1, i-1) && preorder(i, dr);
}
void allBstPreorders(int N) {
for(int i = 1; i <= N; i++)
v.push_back(i);
do{
if(preorder(0,N-1)){
for(int j = 0 ; j < N; j++)
cout<<v[j]<<" ";
cout<<endl;
}
}while( next_permutation( v.begin(),v.end() ) );
}
ifstream fin("planeta.in");
ofstream fout("planeta.out");
int N,k;
int main() {
fin >> N>>k;
for(int i = 1; i <= N; i++)
v.push_back(i);
do{
if(preorder(0,N-1)){
k--;
if(!k){
for(int j = 0 ; j < N; j++)
fout<<v[j]<<" ";
return 0;
}
}
}while( next_permutation( v.begin(),v.end() ) );
fin.close();
fout.close();
return 0;
}