Cod sursa(job #2899649)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 9 mai 2022 00:25:54
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream fin("planeta.in");
ofstream fout("planeta.out");

unsigned long long nrMaxBst[31], query, sum;
int i, j, noduri;
bool gasitSum;

vector <int> rez;

void rsd(int st, int dr, int combDreapta)
{
    if (rez.size() == noduri)
        return;
    if(st == dr)
    {
        rez.push_back(st);
        return;
    }

    for (int j = st; j <= dr; j++)
    {
        if (rez.size() == noduri)
        return;
        sum += nrMaxBst[dr-j] * nrMaxBst[j-st] * nrMaxBst[combDreapta];
        if (sum >= query && (!gasitSum || j==dr))
        {
            if (sum == query)
                gasitSum = 1;
            sum -=nrMaxBst[dr-j] * nrMaxBst[j-st] * nrMaxBst[combDreapta];
            rez.push_back(j);
            rsd(st, j-1, dr-j);
            rsd(j+1, dr, 0);
            break;
        }
    }

}
int main()
{
    //cout << "sunt frumos";
    fin >> noduri >> query;
    nrMaxBst[0] = 1;
    nrMaxBst[1] = 1;
    for (i = 2; i <= noduri; i++)
        for (j = 0; j < i; j++)
            nrMaxBst[i] = 0LL + nrMaxBst[i] + nrMaxBst[j] * nrMaxBst[i-j-1];
    --i;
    rsd(1, noduri, 0);
    for (auto i : rez)
        fout << i << ' ';
    return 0;
}