Pagini recente » Cod sursa (job #1942800) | Cod sursa (job #911954) | Cod sursa (job #2954280) | Cod sursa (job #1201454) | Cod sursa (job #3128982)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<vector<int>> memoizare;
int numaraArbori(int start, int sfarsit) {
if (start > sfarsit) {
return 1;
}
if (memoizare[start][sfarsit] != -1) {
return memoizare[start][sfarsit];
}
int numar = 0;
for (int i = start; i <= sfarsit; ++i) {
numar += numaraArbori(start, i - 1) * numaraArbori(i + 1, sfarsit);
}
memoizare[start][sfarsit] = numar;
return numar;
}
void gasesteAlKlea(int start, int sfarsit, int K, vector<int> &rezultat) {
if (start > sfarsit) {
return;
}
for (int i = start; i <= sfarsit; ++i) {
int numarStanga = numaraArbori(start, i - 1);
int numarDreapta = numaraArbori(i + 1, sfarsit);
if (K <= numarStanga * numarDreapta) {
rezultat.push_back(i);
gasesteAlKlea(start, i - 1, (K - 1) / numarDreapta + 1, rezultat);
gasesteAlKlea(i + 1, sfarsit, (K - 1) % numarDreapta + 1, rezultat);
break;
} else {
K -= numarStanga * numarDreapta;
}
}
}
int main() {
ifstream fin("planeta.in");
ofstream fout("planeta.out");
int N, K;
fin >> N >> K;
memoizare = vector<vector<int>>(N + 2, vector<int>(N + 2, -1));
numaraArbori(1, N);
vector<int> rezultat;
gasesteAlKlea(1, N, K, rezultat);
for (int valoare : rezultat) {
fout << valoare << ' ';
}
fout << '\n';
fin.close();
fout.close();
return 0;
}