Cod sursa(job #403856)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 25 februarie 2010 14:16:52
Problema Planeta Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<iostream>
#include<string>
#include<ctime>

using namespace std;

#define LL long long
#define NM 35

LL P[NM],D[NM][NM];

void solve(int n,LL k,int cat)
{
     if(!n) return ;
     
     LL sum=0,lsum=0;
     
     for(int i=1;i<=n;++i)
     {
          lsum=sum;
          sum+=D[n][i];   
          
          if(lsum<k && k<=sum)
          {
               printf("%d ",i+cat);
               
               LL knou=k-lsum;
               
               LL r1=knou/P[n-i];
               if(knou%P[n-i]) ++r1;
               
               LL r2=knou%P[n-i];
               if(!r2) r2=P[n-i];
               
               solve(i-1,r1,cat);
               solve(n-i,r2,i+cat);
               break;     
          }
     }
}

int main()
{
    int N;
    LL K;
    
    freopen("planeta.in","r",stdin);
    freopen("planeta.out","w",stdout);
    
    scanf("%d %I64d",&N,&K);
    
    P[0]=1;
    P[1]=1;
    D[1][1]=1;
    
    for(int i=2;i<=N;++i)
    {
       for(int j=1;j<=i;++j)
       {
          D[i][j]=P[j-1]*P[i-j];
          P[i]+=D[i][j];
       }   
    }
    
    solve(N,K,0);
    
    return 0;
}