Cod sursa(job #2899629)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 8 mai 2022 23:42:34
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

long long n,k,nr_catalan[65];

void recurs(long long st, long dr, long long aux)
{
    int root;

    root = st;

    while (root < dr && aux-nr_catalan[root-st]*nr_catalan[dr-root] >= 0)
    {
        aux -= nr_catalan[root-st] * nr_catalan[dr-root];
        root++;
    }

    out<<root<<" ";

    if (root > st)   recurs(st, root-1, aux/nr_catalan[dr-root]);
    if (root < dr)   recurs(root+1, dr, aux%nr_catalan[dr-root]);
}

int main()
{
    in>>n>>k;

    nr_catalan[0] = 1;

    for (int i = 1; i<=64; i++)
        for (int j = 1; j<=i; j++)
            nr_catalan[i] += nr_catalan[j-1] * nr_catalan[i-j];

    recurs(1, n, k - 1);

    return 0;
}