Cod sursa(job #3135629)

Utilizator alexandramocanu181Mocanu Alexandra alexandramocanu181 Data 3 iunie 2023 20:57:03
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("planeta.in");
std::ofstream fout("planeta.out");

std::vector<long long> dp(35);
std::vector<int> ans(40);
int pos;

void calculate(int n, long long k, int m)
{
    if (n == 0)
        return;

    int current = 1;
    while (k >= dp[current - 1] * dp[n - current])
    {
        k -= dp[current - 1] * dp[n - current];
        current++;
    }

    ans[++pos] = current + m;
    calculate(current - 1, k / dp[n - current], m);
    calculate(n - current, k % dp[n - current], m + current);
}

int main()
{
    long long n, k;
    fin >> n >> k;
    dp[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    k--;
    calculate(n, k, 0);

    for (int i = 1; i <= n; i++)
        fout << ans[i] << " ";

    return 0;
}