#include <stdio.h>
#define Maxn 2000

struct node{
        __int64    n,b,bn;
       }m,u,d,l,r,ul,ur,dl,dr;

struct ansnode{
        __int64    c,l;
       }now,ans[Maxn];
 __int64    ll;
 __int64    t[Maxn];
 __int64    c[Maxn];
 long  n , total;

__int64   abs( __int64    a){
     if (a>0) return a;
     return -a;
     }
     
 __int64    max( __int64    a, __int64    b){
     if (a<b) a=b;
     return a;
     }

 __int64    max( __int64    a,  __int64    b,  __int64    c,  __int64    d){
     if (a<b) a=b; 
     if (a<c) a=c; 
     if (a<d) a=d;
     return a;
     }

 __int64    min( __int64    a,  __int64    b,  __int64    c,  __int64    d, __int64    e){
     if (a>b) a=b; 
     if (a>c) a=c;
     if (a>d) a=d;
     if (a>e) a=e;
     return a;
     }

void inp(){
          long  x,y;
          n=0;
          scanf("%ld %ld",&x,&y);
          while (x!=0 || y!=0) {
                n++;
                t[n]=y;
                c[n]=x;
                scanf("%ld %ld",&x,&y);
                if (n>1000) break;
                }
          while (x!=0 || y!=0) scanf("%ld %ld",&x,&y);  
          t[0]=ll;
          c[0]=0;
          t[n+1]=ll;
          t[n+1]=0;
          }
     
void prepare(){
      __int64    s, i;
     u.n=-ll+1; u.bn=1; u.b=0;
     l.n=0;    l.bn=ll; l.b=0;
     m.n=1;    m.bn=1;  m.b=1;
     r.n=2;    r.bn=2;  r.b=1;
    
     now.c=0;
     
     if (t[1]==1){
        r.n=2;
        r.bn=1;
        r.b=2;
        }
     s=0; i=0;
     while (s<=ll || i>n){
           i++;
           s+=t[i];
           }
     s-=ll;
     d.n=ll+1; d.bn=t[i]-s+1; d.b=i;
     

     if (d.n!=n+1) now.c=max(now.c,abs(c[d.b]-c[m.b]));

     if (ll!=1) now.c=max(now.c,abs(c[r.b]-c[m.b]));

     if (d.b!=n+1 && ll!=1) 
        if (d.bn==t[d.b]) now.c=max(now.c,abs(c[d.b+1]-c[m.b]));
        
     now.l=1;
     c[n+1]=-100000000;
     t[n+1]=ll;
     } 
     
     
     
void promote(node &k,  __int64    l){
     k.bn+=l;
     k.n+=l;
     if (k.bn>t[k.b]){
        k.b++;
        k.bn=1;
        }
     }
        
     
 __int64    calc(){
     if (m.b==n+1) return -1;
      __int64    max1;
     max1=0; 
     if (u.b!=0)   max1=max(max1,abs(c[u.b]-c[m.b]));
     if (l.n%ll!=0)   max1=max(max1,abs(c[l.b]-c[m.b]));
     if (r.n%ll!=1) max1=max(max1,abs(c[r.b]-c[m.b]));
     if (d.b!=n+1) max1=max(max1,abs(c[d.b]-c[m.b]));
     
     
     if (m.n>ll){
        if (u.bn==1 && m.n%ll!=1) max1=max(max1,abs(c[u.b-1]-c[m.b]));
        if (u.b!=n && u.bn==t[u.b] && m.n%ll!=0) max1=max(max1,abs(c[u.b+1]-c[m.b]));
        }
           
     if (d.b!=n+1){
        if (d.bn==1 && m.n%ll!=1) max1=max(max1,abs(c[d.b-1]-c[m.b]));
        if (d.b!=n && d.bn==t[d.b] && m.n%ll!=0) max1=max(max1,abs(c[d.b+1]-c[m.b]));
        }
           
     return max1;
     }
     
void add( __int64    del , __int64    col){
     if (col==now.c){
        now.l+=del;
 
        return ;
        }
     total++;
     ans[total].c=now.c; 
     ans[total].l=now.l;
     

     now.l=del;
     now.c=col;
     }

     
void work(){
     prepare();
      __int64    del , col;
     while (1) {
           del=min(abs(t[m.b]-m.bn),abs(t[u.b]-u.bn),abs(t[d.b]-d.bn),abs(t[l.b]-l.bn),abs(t[r.b]-r.bn));
           if (m.n>ll){
                     if (u.bn==1 && m.n%ll!=1) del=0;
                     if (u.bn==t[u.b] && m.n%ll!=0) del=0;
                     }
           
           if (d.b!=n+1){
                     if (d.bn==1 && m.n%ll!=1) del=0;
                     if (d.bn==t[d.b] && m.n%ll!=0) del=0;
                     }
           
           if (del==0) del=1;
    
           promote(u,del);
           promote(d,del);
           promote(l,del);
           promote(m,del);
           promote(r,del);
           col=calc();
    
           add(del,col);
           if (m.b==n+1) return ;
           
           if (total> 1000) return ;
           }
     }
     
     
void out(){
           printf("%I64d\n",ll);
            long  i;
           for (i=1; i<=total; i++)      printf("%I64d %I64d\n",ans[i].c, ans[i].l);
           printf("0 0\n");
           } 

int main(){
     long i;
  //  freopen("1009.in","r",stdin);
  //  freopen("1009.out","w",stdout);
    scanf("%I64d",&ll);
    while (ll!=0){
          total=0;
          inp();
          if (n>1000){ scanf("%I64d",&ll); continue; }
          work();
          if (total<=1000) out();
          scanf("%I64d",&ll);
          }
    printf("0\n");
  //  fclose(stdout);
    return 0;
}

• Re:小人写了个o(n) 的程序，sample 过了，但是莫名的run time error...... 那位大牛能帮帮忙？不胜感谢（如果有测试数据，请发到qmczcn@sohu.com) (5077) piratelzs 2006-01-22 09:46:15
  • Re:小人写了个o(n) 的程序，sample 过了，但是莫名的run time error...... 那位大牛能帮帮忙？不胜感谢（如果有测试数据，请发到qmczcn@sohu.com) (0) darklord 2006-11-27 21:46:33
  • Re:小人写了个o(n) 的程序，sample 过了，但是莫名的run time error...... 那位大牛能帮帮忙？不胜感谢（如果有测试数据，请发到qmczcn@sohu.com) (0) lshguang89 2008-07-15 15:25:26
• _int 64应该不行 要用long long (0) glasswm 2008-07-21 09:49:32