Cod sursa(job #2751656)

Utilizator XeinIonel-Alexandru Culea Xein Data 15 mai 2021 15:06:32
Problema Planeta Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>

std::ifstream f("planeta.in");
std::ofstream g("planeta.out");

short Preordine[31];
long long Nr_arbori[31];
short N;
long long K;

void constr_Arbore(short min_nod, short max_nod, long long k, short poz)
{
    if(min_nod <= max_nod)
    {
        Preordine[poz] = min_nod;
        short Nr_Noduri_st = Preordine[poz] - min_nod;
        short Nr_Noduri_dr = max_nod - Preordine[poz];

        while(Nr_arbori[Nr_Noduri_st] * Nr_arbori[Nr_Noduri_dr] < k)
        {
            k -= Nr_arbori[Nr_Noduri_st] * Nr_arbori[Nr_Noduri_dr];
            ++Preordine[poz];
            ++Nr_Noduri_st;
            --Nr_Noduri_dr;
        }

        long long k_st = 1;
        long long Nr_arb_dr = Nr_arbori[Nr_Noduri_dr];
        while(Nr_arb_dr < k)
        {
            k -= Nr_arb_dr;
            ++k_st;
        }

        constr_Arbore(min_nod, Preordine[poz] - 1, k_st, poz + 1);
        constr_Arbore(Preordine[poz] + 1, max_nod, k, poz + Nr_Noduri_st + 1);
    }
}

int main()
{
    f >> N >> K;
    Nr_arbori[0] = Nr_arbori[1] = 1;
    for(int i = 2; i < N; ++i)
        Nr_arbori[i] = Nr_arbori[i-1] * (4 * i - 2) / (i + 1);

    constr_Arbore(1, N, K, 1);

    for(int i = 1; i <= N; ++i)
        g << Preordine[i] << ' ';

    return 0;
}