Cod sursa(job #3132386)

Utilizator Nicoleta114Caramaliu Nicoleta Nicoleta114 Data 22 mai 2023 16:38:55
Problema Planeta Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
using namespace std;

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

long long catalan_nr(int n) {
    if (n == 0) {
        return 1;
    }

    long long catalan = 0;
    for (int i = 0; i < n; i++) {
        catalan += catalan_nr(i) * catalan_nr(n - i - 1);
    }
    return catalan;
}

void gasesteK(int n, long long k, int m) {
    if (n == 0) {
        return;
    }

    int crt = 1;
    while (k >= catalan_nr(crt - 1) * catalan_nr(n - crt)) {
        k -= catalan_nr(crt - 1) * catalan_nr(n - crt);
        crt++;
    }

    g << crt + m << " ";
    gasesteK(crt - 1, k / catalan_nr(n - crt), m);
    gasesteK(n - crt, k % catalan_nr(n - crt), m + crt);
}

int main() {
    long long n, k;
    f >> n >> k;

    gasesteK(n, k - 1, 0);

    f.close();
    g.close();
    return 0;
}