Cod sursa(job #2898485)

Utilizator Nicolae11Mihaila Nicolae Nicolae11 Data 6 mai 2022 22:48:07
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("planeta.in");
ofstream g("planeta.out");
int n;
long long k,cat[32];

void Gen_Catalan(int n)
{   cat[0]=cat[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            cat[i]=cat[i]+cat[i-j]*cat[j-1];
    return;
}

void planeta(int st, int dr, long long k)
{   if(st>dr)
        return;
    int i;
    for (i=st; cat[i-st]*cat[dr-i]<=k && i<=dr; i++)
        k=k-cat[i-st]*cat[dr-i];
    g<<i<<' ';
    if (i>st)
        planeta(st,i-1,k/cat[dr-i]);
    if (i<dr)
        planeta(i+1,dr,k%cat[dr-i]);
    return;
}

int main()
{   f>>n>>k;
    Gen_Catalan(n);
    planeta(1,n,k-1);
    return 0;
}