Cod sursa(job #2899335)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 mai 2022 16:00:38
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

static const int N = 2 << 4;

int catalan[N];

void genCatalan(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];
}

void create(int left, int right, int k) {
    if (left > right)
        return;
    int i;
    for (i = left; i <= right && catalan[i - left] * catalan[right - i] <= k; i++)
        k -= (catalan[i - left] * catalan[right - i]);
    fout << i << " ";

    if (i > left)
        create(left, i - 1, k / catalan[right - i]);
    if (i < right)
        create(i + 1, right, k / catalan[i - left]);
}

int main() {
    // CATALAN(N) = (2N)! / ((N+1)! * (N!))
    int n, k;
    fin >> n >> k;
    genCatalan(n);
    create(1, n, k - 1);

    return 0;
}