Cod sursa(job #2752165)

Utilizator Teodora67IDKIDKIDKDIKD Teodora67 Data 16 mai 2021 22:25:10
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

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

const int Dim = 35;
int n;
long long k;
long long Catalan[Dim];


void Solve(int st, int n, long long k)
{


    if ( n == 0)
        return ;
    if ( n == 1 )
    {

        fout << st + 1 << " ";

        return;

    }
    for ( int i = 1; i <= n; ++i)
    {
        if ( Catalan[i - 1] * Catalan[n - i] >= k )
        {

            fout << st + i << " ";

            Solve(st, i - 1, ( k - 1) / Catalan[n - i]  + 1 );

            Solve(st+ i, n- i,(k - 1) %Catalan[n - i] + 1);

            return;
        }

        k -= Catalan[i - 1] * Catalan[n - i];

    }

}
void Dyanamic()
{

    Catalan[0] = 1;
    for ( int i = 1; i <= n; ++i)
        for ( int j = 1; j <= i ; ++j)
            Catalan[i] += Catalan[i - j] * Catalan[j-1];
}

int main()
{
    fin >> n >> k;
    Dyanamic();
    Solve(0,n,k);

}