Cod sursa(job #3135987)

Utilizator Ioana.SilviaLeahu Silvia-Ioana Ioana.Silvia Data 4 iunie 2023 22:19:52
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;

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

long long int t[31], N, K;

void generate(long long int left,long long int right,long long int k ){
    //intotdeauna voi avea un interval de numere pe care va trebui
    //sa le ordonez in diferite moduri pentru a genera arbori
    long long int i, posibilities, newright, newleft;

    for( i = left; i<= right; i++){
        posibilities = t[i - left]*t[ right - i]; //unesc doi subarbori fiecare avand deja posibilitatile lui de ordonare, asa ca pt a afla posibilitatile arborelui mare, inmultesc cele doua numere
        ///elimin redundanta(daca posibilitatile sunt mai putinee decat k
        ///va insemna ca subarborele in care ne aflam este redundant, asa ca reducem k pana la numarul dorit)

        if (posibilities <= k)
            k = k-posibilities;
        else{
            g << i <<" ";
            if (i >left)
                generate(left,i-1, k/t[right-i]);
            if (i<right)
                generate(i+1, right, k%t[right-i]);
            break;
        }

    }

}

int main() {
///calculam numarul de arbori care pot fi formati cu n noduri, care aparent se poate calcula cu  formula urmatoare : t(n) = suma de la i la n t(i-1)t(n-1)
f >> N;
t[0] = 1;
t[1] = 1;
for (int n = 2; n <=N; n++)
    for (int i = 0; i <= n; i++ )
        t[n]+= t[i-1]*t[n-i];

f >> K;
generate(1,N,K-1);
    return 0;
}