Cod sursa(job #2899622)

Utilizator RaduAntoneoAntonio Alexandru Radu RaduAntoneo Data 8 mai 2022 23:33:40
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("planeta.in");
ofstream g("planeta.out");
#define cin f
#define cout g

int n;
long long k, catalan[32];

void planeta(int st, int dr, long long k) {
    int i;
    if( st > dr)
        return;
    for(i = st; catalan[i - st] * catalan[dr - i] <= k && i <= dr; i++)
        k = k - catalan[i - st] * catalan[dr - i];
    cout << i <<' ';
    if(i > st)
        planeta(st, i - 1, k / catalan[dr - i]);
    if(i < dr)
        planeta(i + 1, dr, k % catalan[dr - i]);
    return;
}

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