Pagini recente » Cod sursa (job #2352782) | Cod sursa (job #2756308) | Cod sursa (job #2607198) | Cod sursa (job #666229) | Cod sursa (job #3234788)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// Funcție pentru a insera un nod într-un BST
TreeNode* insertBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val) root->left = insertBST(root->left, val);
else root->right = insertBST(root->right, val);
return root;
}
// Funcție pentru a genera traversarea în pre-ordine a unui BST
void preOrderTraversal(TreeNode* root, vector<int>& traversal) {
if (!root) return;
traversal.push_back(root->val);
preOrderTraversal(root->left, traversal);
preOrderTraversal(root->right, traversal);
}
// Funcție pentru a genera toate permutările și a construi BST-urile
void generatePermutations(int N, int K, vector<int>& result) {
vector<int> nums(N);
iota(nums.begin(), nums.end(), 1); // Umplem nums cu 1, 2, ..., N
vector<vector<int>> traversals;
do {
TreeNode* root = NULL;
for (int num : nums) {
root = insertBST(root, num);
}
vector<int> traversal;
preOrderTraversal(root, traversal);
traversals.push_back(traversal);
} while (next_permutation(nums.begin(), nums.end()));
// Sortăm traversările în pre-ordine lexicografic
sort(traversals.begin(), traversals.end());
// Returnăm a K-a traversare în pre-ordine
result = traversals[K - 1];
}
int main() {
ifstream inFile("planeta.in");
ofstream outFile("planeta.out");
int N, K;
inFile >> N >> K;
vector<int> result;
generatePermutations(N, K, result);
for (int val : result) {
outFile << val << " ";
}
outFile << endl;
return 0;
}