Cod sursa(job #2010186)

Utilizator TincaMateiTinca Matei TincaMatei Data 12 august 2017 00:30:08
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

//preinitializare ftw
long long mods[31] = {1LL, 1LL, 2LL, 5LL, 14LL, 42LL, 132LL, 429LL, 1430LL, 4862LL, 16796LL, 58786LL, 208012LL, 742900LL, 2674440LL, 9694845LL, 35357670LL, 129644790LL, 477638700LL, 1767263190LL, 6564120420LL, 24466267020LL, 91482563640LL, 343059613650LL, 1289904147324LL, 4861946401452LL, 18367353072152LL, 69533550916004LL, 263747951750360LL, 1002242216651368LL, 3814986502092304LL};

int v[31];

void gen(int stvec, int drvec, int stv, int drv, long long k) {
  int st = 0, dr = drv - stv, n = dr + 1;
  if(stvec <= drvec) {
    long long sum = 0LL;
    while(st <= dr && sum <= k) {
      sum = sum + mods[st] * mods[n - st - 1];
      ++st;
    }
    --st;
    sum = sum - mods[st] * mods[n - st - 1];
    k -= sum;

    v[stvec] = stv + st;
    gen(stvec + 1, stvec + st, stv, stv + st - 1, k / mods[n - st - 1]);
    gen(stvec + 1 + st, drvec, stv + st + 1, drv, k % mods[n - st - 1]);
  }
}

int main() {
  int n;
  long long k;
  FILE *fin = fopen("planeta.in", "r");
  FILE *fout = fopen("planeta.out", "w");
  fscanf(fin, "%d%lld", &n, &k);
  gen(1, n, 1, n, k - 1);
  for(int i = 1; i <= n; ++i)
    fprintf(fout, "%d ", v[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}