Cod sursa(job #2899515)

Utilizator T_george_TGeorge Teodorescu T_george_T Data 8 mai 2022 21:41:00
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb

#include <iostream>
#include <fstream>

using namespace std;

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

long long catalan[31];

void sol(long long st, long dr, long long r) {
    int rad;
    rad = st;
    if (st > rad)
        return;
    while (rad < dr && r - catalan[rad - st] * catalan[dr - rad] >= 0) {
        r -= catalan[rad - st] * catalan[dr - rad];
        rad++;
    }
    out << rad << ' ';
    if (rad > st)
        sol(st, rad - 1, r / catalan[dr-rad]);
    if (rad < dr)
        sol(rad + 1, dr, r % catalan[dr-rad]);
}

int main() {
    int n;
    long long k;
    in >> n >> k;
    catalan[0] = 1;
    for (int i = 1; i <= 30; i++)
        for (int j = 1; j <= i; j++)
            catalan[i] += catalan[j - 1] * catalan[i - j];
    sol(1, n, k - 1);
    return 0;
}