Pagini recente » Cod sursa (job #1788899) | Cod sursa (job #263683) | Cod sursa (job #2673802) | Cod sursa (job #2983878) | Cod sursa (job #2898208)
#include <fstream>
#include <array>
using namespace std;
//ma doare fizic sa fac functii si variabile globale
//dar altfel recursia ar fi foarte greu de facut
// si mi-e lene sa fac iterativ acum
array<int, 30> preorder;
array<pair<int, int>, 30> ranges;
array<long long, 31> catalanNrs;
ifstream in("planeta.in");
ofstream out("planeta.out");
void afis(int n)
{
for (int i = 0; i < n; ++i)
out << preorder[i] << " ";
}
void kthPreorder(int pos,long long k)
{
static long long count = 0;
const int lower_bound = ranges[pos].first;
const int upper_bound = ranges[pos].second;
for(int i = lower_bound; i < upper_bound; ++i)
{
if (count == k)
{
afis(ranges[0].second);
exit(0);
}
preorder[pos] = i + 1;
if (pos == ranges[0].second - 1)
++count;
if(i - lower_bound > 0)
ranges[pos + 1] = { lower_bound, i};
if(upper_bound- i - 1 > 0)
ranges[pos + i - lower_bound + 1] = { i + 1, upper_bound };
kthPreorder(pos + 1, k);
}
}
void computeCatalan(int n)
{
catalanNrs[0] = catalanNrs[1] = 1;
for (int i = 2; i <= n; ++i)
{
catalanNrs[i] = 0;
for (int j = 0; j < i; ++j)
catalanNrs[i] += catalanNrs[j] * catalanNrs[i - j - 1];
}
}
int main()
{
int n;
long long k;
in >> n >> k;
in.close();
computeCatalan(n);
ranges[0] = {0,n};
kthPreorder(0,k);
return 0;
}