Cod sursa(job #2253620)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 4 octombrie 2018 10:49:04
Problema Planeta Scor 100
Compilator cpp Status done
Runda shimulare_shmecheri Marime 1.22 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("planeta.in");
ofstream out ("planeta.out");

#define ll long long

int const nmax = 30;

ll dp[5 + nmax][5 + nmax];///trees with i nodes ,  root
ll sum[5 + nmax];

int n;

void computedp(){
  dp[0][0] = 1;

  sum[0] = 1;

  for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= i ;j ++){
      dp[i][j] = sum[j - 1] * sum[i - j];
      sum[i] += dp[i][j];
      //cout << i << " " << j << " " << dp[i][j] << '\n';

    }
  }
}

void print(int start , int sz , ll k){
  //cout << '\n' << start << " " << sz << " " << k << '\n';

  if(sz == 0)
    return ;

  if(sz == 1){
    out << start + 1 << " ";
  } else {

    for(int i = 1 ; i <= sz ; i++){

      //cout << i << " " << sum[i - 1] << " " <<  sum[sz - i] << '\n';

      if(sum[i - 1] * sum[sz - i] >= k){
        out << start + i << " " ;
        print(start , i - 1 , (k - 1) / sum[sz - i] + 1);
        print(start + i, sz - i, (k - 1) % sum[sz - i] + 1);
        return ;
      }
      k -= sum[i - 1] * sum[sz - i];
    }
    //cout << ":";

  }
}

int main()
{
  ll  k;
  in >> n >> k;
  computedp();

  print(0 , n , k);

  return 0;
}