Cod sursa(job #2897880)

Utilizator RobertuRobert Udrea Robertu Data 5 mai 2022 10:16:08
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
std::fstream fin("planeta.in");
std::ofstream fout("planeta.out");

const int dim = 32;
int n;
long long  catalan[dim], k;

void rez(int st, int dr, long long kk) {
    int i;
    for(i = st; catalan[i - st] * catalan[dr - i] <= kk && i <= dr; i++) 
        kk -= catalan[i - st] * catalan[dr - i];
    fout << i << ' ';

    if(i > st) rez(st, i - 1, kk / catalan[dr - i]);
    if(i < dr) rez(i + 1, dr, kk % catalan[dr - i]);
}

int main() {
    fin >> n >> k;
    catalan[0] = catalan[1] = 1;
    for(int i = 2; i <= n; i++) for(int j = 0; j < i; j++) catalan[i] += catalan[j] * catalan[i - j - 1];
    
    rez(1, n, --k);

    //Pentru varianta de pe csacademy
    // for(int i = 0; i < catalan[n]; i++) {
    //     rez(1, n, i);
    //     std::cout << '\n';
    // }

    return 0;
}