Cod sursa(job #2898797)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 7 mai 2022 12:29:08
Problema Planeta Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

int n;
long long k;

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

int combinari(int n, int k)
{
    int comb = 1, i;
    if(n - k < k)
        k = n - k;
    for(i = 1; i <= k; i++)
    {
        comb *= (n - k + i);
        comb /= i;
    }
    return comb;
}

int catalan(int n)
{
    return combinari(2 * n, n) / (n + 1);
}

void k_parcurgere(int st, int dr, int ramas)
{
    int rad, ok = 1;
    if(st > dr) exit(0);
    rad = st;
        while(rad <= dr && ramas - catalan(rad-st)*catalan(dr-rad) >= 0)
        {
            ramas -= catalan(rad-st)*catalan(dr-rad);
            rad++;
        }
    g << rad << ' ';
    if(rad > st)
        k_parcurgere(st, rad - 1, ramas / catalan(dr - rad));
    if(rad < dr)
        k_parcurgere(rad + 1, dr, ramas % catalan(dr - rad));
}

int main()
{int n, k;
f >> n >> k;
k_parcurgere(1, n, k - 1);
f.close();
g.close();
return 0;
}