Cod sursa(job #2277425)

Utilizator theoioanaTheodoraD theoioana Data 6 noiembrie 2018 11:08:10
Problema Planeta Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
// https://infoarena.ro/problema/planeta

#include <iostream>
#include <fstream>

using namespace std;

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

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

void BST_CATALAN(int st, int n, long long k);
void Dyanamic();

/*void catalan(int n)
{

    int cat;

    for(i=1 ; i<=n; i++)
    {
        cat += catalan(i)*catalan(n-i-1);
    }

    return cat;

}*/

int main()
{

	fin>>n;
	fin>>k;

	Dyanamic();

	BST_CATALAN(0,n,k);

	return 0;

}

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];

		}

    }

}

void BST_CATALAN(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<<" ";

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

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

			return;

		}

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

	}

}