Pagini recente » Cod sursa (job #1636279) | Cod sursa (job #2220202) | Cod sursa (job #1443549) | Cod sursa (job #2856838) | Cod sursa (job #2277425)
// 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];
}
}