Cod sursa(job #2514718)

Utilizator hrazvanHarsan Razvan hrazvan Data 26 decembrie 2019 18:05:03
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#define MAXN 30
long long dt[MAXN + 1], d[MAXN + 1][MAXN + 1];
int v[MAXN], dv;
char fol[MAXN + 1];

void precalc(){
  int i, j;
  dt[0] = dt[1] = 1;
  d[1][1] = 1;
  for(i = 2; i <= MAXN; i++){
    for(j = 1; j <= i; j++){
      d[i][j] = 1LL * dt[j - 1] * dt[i - j];
      dt[i] += d[i][j];
    }
  }
}

void calc(int n, long long k){
  if(n > 0){
    int i = 1;
    while(d[n][i] < k){
      k -= d[n][i];
      i++;
    }
    v[dv++] = i;
    long long x, y;
    x = k / dt[n - i];
    y = k % dt[n - i];
    if(y == 0)
      x--, y = dt[n - i];
    calc(i - 1, x + 1);
    calc(n - i, y);
  }
}

int main(){
  freopen("planeta.in", "r", stdin);
  freopen("planeta.out", "w", stdout);
  int n, i, j;
  long long k;
  scanf("%d%lld", &n, &k);
  precalc();
  calc(n, k);
  for(i = 0; i < n; i++){
    for(j = 1; v[i] - (!fol[j]) > 0; j++)
      v[i] -= (!fol[j]);
    fol[j] = 1;
    v[i] = j;
    printf("%d ", v[i]);
  }
  return 0;
}