Cod sursa(job #2189531)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 28 martie 2018 16:07:03
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream fin ("planeta.in");
ofstream fout ("planeta.out");
int n,i,j;
long long k,d[40];
void rec (int st, int dr, long long k){
    if (st > dr)
        return;
    long long total = 0;
    for (int r = st; r <= dr; r++){
        total = d[r-st] * d[dr-r];
        if (k > total)
            k -= total;
        else{
            /// imi mai trebuie k-total arbori
            fout<<r<<" ";
            long long nst,ndr;
            nst = k/d[dr-r];
            if (k%d[dr-r])
                nst ++;
            if (k%d[dr-r])
                ndr = k % d[dr-r];
            else
                ndr = d[dr-r];
            rec (st,r-1,nst);
            rec (r+1,dr,ndr);
            return;
        }
    }
    return;
}

int main (){

    fin>>n>>k;
    /// d[i] - cati arbori de cautare cu i noduri exista
    /// adica practic avem catalan
    d[0] = 1;
    for (i=1;i<=n;i++)
        for (j=0;j<=i;j++)
            d[i] += d[j] * d[i-j-1];

    rec (1,n,k);


    return 0;
}