//---------------------------------------------------------------------------
/*---------------------------------------------------------

	Problem:        A decorative fence
	Author:		gogo@ccnu
	Algorithm:	DP
	Complexity:	0(n^2)

        some tips:
        1.up(N,N) = down(N,1) = 0;
        2.up(N,i) = down(N,N+1-i);
        3.down(N,i) = down(N,i-1) + up(N-1,i-1);

---------------------------------------------------------*/
#include <stdio.h>

long long T,N;
long long C;
long long a[21];
long long up[21][21];
long long down[21][21];

void print();
void init()
{
  up[1][1] = 1;
  for(long long i=2;i<=20;i++)
  {  long long j;
     for(j=2;j<=i;j++)
       down[i][j] = down[i][j-1] + up[i-1][j-1];
 
     for(j=1;j<i;j++)
       up[i][j] = down[i][i+1-j];

// print();
  }
}

void go_up(long long n,long long c,long long lmt);
void go_down(long long n,long long c,long long lmt)
{
  if(n==1) {printf(" %d",a[n]);return;}

  for(long long i=lmt;i<=n;i++)
  {
   c -= down[n][i];
   if(c<1)
   {
    printf(" %d",a[i]);
    for(long long j=i;j<=n;j++) a[j] = a[j+1];
    go_up(n-1,c+down[n][i],i-1);
    break;
   }
  }
}
void go_up(long long n,long long c,long long lmt)
{
 if(n==1) {printf(" %d",a[n]);return;}

  for(int i=1;i<=lmt;i++)
  {
   c -= up[n][i];
   if(c<1)
   {
    printf(" %d",a[i]);
    for(int j=i;j<=n;j++) a[j] = a[j+1];
    go_down(n-1,c+up[n][i],i);
    break;
   }
  }
}
void solve(long long n,long long c)
{
  if(n==1) printf("%d",a[n]);

  for(long long i=2;i<=n;i++)
  {
  c -= up[n][i-1];
  if(c<1)
  { 
   printf("%d",a[i-1]);
   for(int j=i-1;j<n;j++) a[j] = a[j+1];
   go_down(n-1,c+up[n][i-1],i-1);
   break;
  }

  c -= down[n][i];
  if(c<1)
  {
   printf("%d",a[i]);
   for(int j=i;j<n;j++) a[j] = a[j+1];
   go_up(n-1,c+down[n][i],i);
   break;
  }
  }
}

int main()
{
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
  init();
  scanf("%Ld",&T);
 
  while(T--)
  {
    scanf("%Ld%Ld",&N,&C);
    for(long long i=1;i<=20;i++) a[i] = i;
      solve(N,C);
    printf("%c",13);
    printf("\n");
  }
  return 1;
}

void print()
{
  int u,v;
  for(u=1;u<=6;u++)
  {  for(v=1;v<=6;v++)
   {  printf("%4d ",up[v][u]);
   
   } printf("\n");
  }
 printf("\n");
  for(u=1;u<=6;u++)
  {  for(v=1;v<=6;v++)
   {  printf("%4d ",down[v][u]);
   
   } printf("\n");
  }   
  printf("------------------\n");
}
//---------------------------------------------------------------------------

• 你第一组数据就不对，不知道你怎么测试的 (2838) hawk 2004-09-23 11:53:45
  • 你代码改成vc的，就pe了，估计是gcc编译器的问题 (54) hawk 2004-09-23 11:57:29
    • 特感动，谢谢haking大大救命， 我昨天折腾了一天，晕闷的要死掉了！ (27) gogo_ccnu 2004-09-23 12:36:39
      • 呵呵，不客气。只是编译器这样有些郁闷 (31) hawk 2004-09-23 15:17:29