Cod sursa(job #3128982)

Utilizator florinilie324Ilie Florin Alexandru florinilie324 Data 11 mai 2023 21:23:41
Problema Planeta Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#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;
}