Cod sursa(job #2898478)

Utilizator andriciucandreeaAndriciuc Andreea andriciucandreea Data 6 mai 2022 22:08:32
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long v[100], x;
int n;

void search(int st, int dr, long long k)
{
    int current;
	for(current = st; current < dr; current++)
    {
        long long nr = v[current - st] * v[dr-current];
        if (nr <= k)
            k -= nr;
        else
            break;
    }
    fout<<current<<' ';
    if(current > st)
        search(st, current - 1, k / v[dr-current]);
    if(current < dr)
        search(current + 1, dr, k % v[dr-current]);

}

int main()
{
    ///Total number of possible Binary Search Trees
    ///with n different keys
    ///(countBST(n)) = Catalan number
    ///Cn = (2n)! / ((n + 1)! * n!)
    fin>>n>>x;
	v[0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			v[i] +=  v[i - j] * v[j - 1];     ///generare de numere catalan
    x--;
    search(1, n, x);
    return 0;
}