Cod sursa(job #2398332)

Utilizator FnZbZVrinceanu Radu FnZbZ Data 5 aprilie 2019 12:46:21
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#define NMAX 32
#include <bits/stdc++.h>
using namespace std;

ifstream fin("planeta.in");
ofstream fout("planeta.out");
unsigned long long m = 1, K, A[NMAX];
int N, x = 1, S[NMAX];

void DP() {
    A[0] = 1;
    for(int i = 1; i <= N; )
        for(int j = 0; j < i; )
            A[i] += A[j] * A[i - j - 1];
}

void chooseBest(int p, int u) {
    if(p > u) return;
    if(p == u) {
        S[p] = x;
        return;
    }

    int cnt = u - p + 1, i = 1;
    long long sum = 0;

    for(i; i <= cnt; i++) {
        if(sum + 1LL * A[i-1] * A[cnt-i] * m >= K) break;
        sum += 1LL * A[i-1] * A[cnt-i] * m;
    }

    K -= sum;
    m *= A[cnt - i];
    chooseBest(p + 1, p + i - 1);
    m /= A[cnt - i];

    x += i;
    chooseBest(p + i, u);
    x -= i;
}

int main()
{
    fin>>N>>K;
    DP();
    chooseBest(1, N);

    for(int i = 1; i <= N; i++)
        fout<<S[i]<<' ';

    fin.close();
    fout.close();
    return 0;
}