Cod sursa(job #1990515)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 12 iunie 2017 12:07:39
Problema Planeta Scor 100
Compilator cpp Status done
Runda Simulare 14b Marime 1.33 kb
#include <fstream>
#include <cassert>

using namespace std;

FILE *fin = fopen ("planeta.in", "r"), *fout = fopen ("planeta.out", "w");

typedef long long i64;

const int nmax = 30;

int v[nmax + 1];
i64 s[nmax + 1], d[nmax + 1][nmax + 1];

void precalc() {
    s[ 0 ] = 1;

    for (int i = 1; i <= nmax; ++ i) {
        for (int j = 1; j <= i; ++ j) {
            d[ i ][ j ] = s[j - 1] * s[i - j];
            s[ i ] += d[ i ][ j ];
        }
    }
}

void solve (int x, int y, i64 k) {
    if (x > y) {
        assert(k == 1);
        return ;
    }

    int rad = 0, lg = y - x + 1;
    for (int i = 1; i <= y - x + 1; ++ i) {
        if (d[ lg ][ i ] < k) {
            k -= d[ lg ][ i ];
        } else {
            rad = i;
            break;
        }
    }

    v[ x ] = rad;

    i64 aux = k / s[lg - rad];
    i64 rest = k % s[lg - rad];

    if (rest == 0) {
        rest = s[lg - rad];
    } else {
        ++ aux;
    }

    int mij = x - 1 + rad;
    solve(x + 1, mij, aux);
    solve(mij + 1, y, rest);

    for (int i = mij + 1; i <= y; ++ i) {
        v[ i ] += rad;
    }
}

int main() {
    precalc();

    int n; i64 k;
    fscanf(fin, "%d%lld", &n, &k);

    solve(1, n, k);

    for (int i = 1; i <= n; ++ i) {
        fprintf(fout, "%d ", v[ i ]);
    }
    fprintf(fout, "\n");

    fclose( fin );
    fclose( fout );
    return 0;
}