Cod sursa(job #2020848)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 11 septembrie 2017 20:07:02
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

const int MAXN = (int) 30;

long long dp[MAXN + 1][MAXN + 1];

std::vector <int> sol;

int n;
long long k;
int cnt = 0;

void dfs(int sz, long long prod, int add) {
    long long sum = 0;
    int i = 1;
    while(sum < k) {
        sum += dp[sz][i] * prod;
        i++;
    }
    i--;
    sol.push_back(i + add);
    k -= (sum - dp[sz][i] * prod);
    sum = 0;
    for(int j = 0; j <= sz - i; j++)
        sum += dp[sz - i][j];
    if(i - 1 >= 1)
         dfs(i - 1, prod * sum, add);
    if(sz - i >= 1)
         dfs(sz - i, prod, add + i);
}

int main() {
    FILE *fi, *fout;
    int i, j, a, b;
    fi = fopen("planeta.in" ,"r");
    fout = fopen("planeta.out" ,"w");
    fscanf(fi,"%d %lld " ,&n,&k);
    dp[0][0] = 1;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= i; j++)
            for(a = 0; a < j; a++)
                for(b = 0; b <= i - j; b++)
                    dp[i][j] += dp[j - 1][a] * dp[i - j][b];
    }
    dfs(n, 1, 0);
    for(auto it : sol)
        fprintf(fout,"%d " ,it);
    fclose(fi);
    fclose(fout);
    return 0;
}