#include <stdio.h>
#include <string.h>
#define MAXN 500100
struct People
{
   char name[12];
   int shift;
}arr[MAXN];
int ant[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,
       15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500100};
       
int ans[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,
        160,168,180,192,200,0};       
       
int mat[MAXN*3];
int tree[MAXN*3];

void init(int left,int right,int v)
{
   tree[v]=right-left+1;
   if(left!=right)
   {
      init(left,(left+right)/2,2*v);
      init((left+right)/2+1,right,2*v+1);
   }
   else mat[v]=left;
}
int main()
{
   int n,k,f,t,left,right,v,count,i;
   while(scanf("%d%d",&n,&k)!=EOF)
   {
      for(i=1;i<=n;i++) scanf("%s%d",arr[i].name,&arr[i].shift);
      memset(mat,0,sizeof(mat));
      init(1,n,1);
      for(t=0;t<36;t++) if(n<ant[t]) break;
      t--;
      for(i=1;i<ant[t];i++)
      {
         left=1,right=n,v=1;
         while(left!=right)
         {
            tree[v]--;
            if(k>(left+right)/2) 
            {
               left=(left+right)/2+1;
               v=v*2+1;
            }
            else 
            {
               right=(left+right)/2;
               v=v*2;
            }
         }
         //if(i==3) printf("%d--\n",v);
         tree[v]--;
         if(arr[k].shift>0)
         {
            f=v/2;
            count=arr[k].shift;
            //if(i==3) printf("%d--\n",count);
            while(f)
            {
               if(v==f*2&&tree[f*2+1]>=count) 
               {
                  v=f*2+1;
                  break;
               }
               if(v==f*2) count-=tree[f*2+1];
               v=f;
               f=v/2;
            }
            //if(i==3) printf("%d--%d--%d\n",v,f,count);
            if(!f) count%=tree[1];
            if(!count) count=tree[1];
            //printf("%d--%d\n",tree[1],count);
            while(!mat[v])
            {
               //printf("%d--\n",v);
               if(tree[v*2]>=count) v=v*2;
               else
               {
                  count-=tree[v*2];
                  v=v*2+1;
               }
            }
            //printf("%d-------------\n",v);
            k=mat[v];
            //printf("%d----\n",k);
         }
         else 
         {
            f=v/2;
            count=-arr[k].shift;
            while(1)
            {
               if(v==f*2+1&&tree[f*2]>=count) 
               {
                  v=f*2;
                  break;
               }
               if(v==f*2+1) count-=tree[f*2];
               v=f;
               f=v/2;
            }
            if(!f) count%=tree[1];
            if(!count) count=tree[1];
            while(!mat[v])
            {
               if(tree[v*2+1]>=count) v=v*2+1;
               else
               {
                  count-=tree[v*2+1];
                  v=v*2;
               }
            }
            k=mat[v];
         }
      }
      printf("%s %d\n",arr[k].name,ans[t]);
   }
   return 0;
}

• 很抱歉我没有帮人看代码的习 (49) gaminerie 2006-08-07 20:09:34
  • 那能不能通过下标判断某个接点是否是叶子呢，还是必须标记呢？ (55) nuanran 2006-08-07 20:20:45
• 或许你是想得太复杂了吧 (3452) frkstyc 2006-08-07 20:11:49
  • 什么意思？ (0) nuanran 2006-08-07 20:21:21
    • 递归一下不很好么 (0) frkstyc 2006-08-07 20:22:24
      • 弱问一下，能不能根据子树的left,right确定父亲的left,right,现在搞晕了．．．． (0) nuanran 2006-08-07 20:46:42
        • 呼，终于过了！把一个while(f)写成while(1)了，还以为我找的时候太笨了，不过再问一下为什么C++会RE,G++就过了呢？ (0) nuanran 2006-08-07 21:09:38
      • 还有结点数最多是N几倍呢？ (0) nuanran 2006-08-07 21:15:15