Cod sursa(job #2898848)

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

using namespace std;

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

long long 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;
}

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

void k_parcurgere(int st, int dr, long long 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;
long long k;
f >> n >> k;
k_parcurgere(1, n, k - 1);
f.close();
g.close();
return 0;
}