Pagini recente » Cod sursa (job #3292353) | Cod sursa (job #965064) | Cod sursa (job #2373546) | Cod sursa (job #903570) | Cod sursa (job #3132379)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("planeta.in");
ofstream g("planeta.out");
vector<long long> catalan_nr(int n) {
vector<long long> catalan(n + 1, 0);
catalan[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
catalan[i] += catalan[j] * catalan[i - j - 1];
}
}
return catalan;
}
string gasesteK(vector<int>& perm, const vector<long long>& catalan, int start, int end, long long k) {
if (start > end) {
return "";
}
int rIndex = start;
while (rIndex < end && k >= catalan[rIndex - start] * catalan[end - rIndex - 1]) {
k -= catalan[rIndex - start] * catalan[end - rIndex - 1];
rIndex++;
}
string t = to_string(perm[rIndex]) + " ";
string leftT= gasesteK(perm, catalan, start, rIndex - 1, k / catalan[end - rIndex - 1]);
string rightT = gasesteK(perm, catalan, rIndex + 1, end, k % catalan[end - rIndex - 1]);
t += leftT + rightT;
return t;
}
int main() {
int N, K;
f >> N >> K;
vector<int> perm(N);
for (int i = 0; i < N; i++) {
perm[i] = i + 1;
}
vector<long long> catalan = catalan_nr(N);
string resultat = gasesteK(perm, catalan, 0, N - 1, K - 1);
g << resultat << endl;
return 0;
}