Cod sursa(job #2899229)

Utilizator elenaa_g23Elena Georgescu elenaa_g23 Data 8 mai 2022 12:40:03
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include<fstream>

using namespace std;

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

int catalan[31];

void Catalan(int n)
{
    catalan[0]=1;
    catalan[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            catalan[i]=catalan[i]+catalan[j-1]*catalan[i-j];

   return;
}

void creare(int stanga, int dreapta, long long k)
{
    int i;
    if(stanga>dreapta)
        return;

    for(i=stanga; i<=dreapta &&  catalan[i-stanga]*catalan[dreapta-i]<=k;i++)
         k-=catalan[i-stanga]*catalan[dreapta-i];

    g<<i<<' ';

    if(i>stanga)
        creare(stanga, i-1, k/catalan[dreapta-i]);
    if(i<dreapta)
        creare(i+1, dreapta, k/catalan[i-stanga]);
    return;
}

int main()
{
    int n;
    long long k;
    f>>n>>k;
    Catalan(n);
    creare(1,n,k-1);

}