Cod sursa(job #1758861)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 17 septembrie 2016 23:32:54
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("planeta.in");
ofstream cout("planeta.out");

const int MAXN = 30;

long long dp[1 + MAXN];

void Solve(int left, int right, long long k) {
    if (left > right)
        return;
    long long value = 0;
    for (int i = left; i <= right; i++) {
        value = value + dp[i - left] * dp[right - i];
        if (value > k) {
            value = value - dp[i - left] * dp[right - i];
            k -= value;
            cout << i << " ";
            Solve(left, i - 1, k / dp[right - i]);
            Solve(i + 1, right, k % dp[right - i]);
            return;
        }
    }
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] = dp[i] + dp[j - 1] * dp[i - j];
    Solve(1, n, k - 1);
    return 0;
}