[题解]Let’s Celebrate the 100th Contest on ZOJ! » ZOJ3445oldjunyi

ZOJ3445oldjunyi
ZOJ3445oldjunyi.c


#define L 10000
#define K printf
#define B(a) {r=a;goto Z;}
#define F(a) for(i=1;i<=*a;i++)
#define G(a) for(i=*a;i>=1;i--)
#define R(a) F(a)if(a[i]>=L)a[i-*a?i+1:++*a]+=a[i]/L,a[i]%=L;
#define S(a) while(!a[*a]&&*a>1)--*a;
#define P(a) a[i+1]+=(a[i]-L+1)/L,a[i]-=(a[i]-L+1)/L*L;
main(){int n;while(scanf("%d",&n)
>0){int p,q,i,a[ 64]={1},c[ 64]={
1},s[ 64]={1},t,r;for(p=c[*c= 61]
=1;q=n+1-p;p++){F(c)c[i]*=p;R(c)G
(c)c[i]+=c[i+1]%q*L,c[i+1]/=q;c[1
]/=q;S(c)memcpy(a,c,256);int k,l,
h,m,b[ 64]={1};for(k=*b=(1+*a)/2;
k;b[k--]+=m){for(l=0,h=L-1,b[k]=m
=L/2;l<h;b[k]=m=(l+h+1)/2){t=0;if
(*a-*b<k-1&&m)B(1)for(i=*a;i>k-1;
i--){t=t*L+b[i-k+1]*m-a[i];if(t>0
)B(1)if(t<-L*2)B(0)}while(i){t=t*
L-a[i--];if(t>0)B(1)if(t<-L*2)B(0
)}r=t>0;Z:r?(h=m-1):(l=m);}for(i=
k+1;i<*b+k+2;i++)if((a[i]-=b[i-k+
1]*m)<0)P(a)for(;a[i]<0;i++)P(a)S
(a)}S(b)F(b)b[i]/=2;F(b)s[i]+=b[i
];if(*b>*s)*s=*b;R(s)}s[31]++;if(
s[ 5]*2>=L)s[ 6]++;R(s)K("%d",s[*
s]);for(i=*s;--i> 5;K(".%04d"+(i-
30?1:0),s[i]));K("\n");}exit(0);}
Leave a Reply