Cod sursa(job #2047958)

Utilizator robx12lnLinca Robert robx12ln Data 25 octombrie 2017 17:34:09
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
unsigned long long catalan[35], k;
int n;
void solve( int st, int dr, unsigned long long k ){
    if( st > dr )
        return;
    for( int i = st; i <= dr; i++ ){
        int L = i - st;
        int R = dr - i;
        if( k > catalan[L] * catalan[R] )
            k -= catalan[L] * catalan[R];
        else{
            fout << i << " ";
            unsigned long long kst, kdr;
            kst = k / catalan[R] + !( k % catalan[R] == 0 );
            kdr = ( k % catalan[R] == 0 ) ? catalan[R] : k % catalan[R];
            solve( st, i - 1, kst );
            solve( i + 1, dr, kdr );
            return;
        }
    }
    return;
}
int main(){
    fin >> n >> k;
    catalan[0] = 1;
    for( int i = 1; i <= n; i++ ){
        for( int j = 0; j <= i; j++ )
            catalan[i] += catalan[i - j - 1] * catalan[j];
    }
    solve( 1, n, k );
    return 0;
}