Cod sursa(job #173673)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 7 aprilie 2008 22:31:32
Problema Next Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#define NMAX 1000UL
#define STRTO  strtoull
//#define	ULTO   ulltoa
#define	NMAX	1000000UL
unsigned long long v10[19]={
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000ULL,
10000000000ULL,
100000000000ULL,
1000000000000ULL,
10000000000000ULL,
100000000000000ULL,
1000000000000000ULL,
10000000000000000ULL,
100000000000000000ULL,
1000000000000000000ULL};

int nc(unsigned long long x)
{
int _nc,i=0,j=18,mij;
while(i<=j){
	mij=(i+j)/2;
	if(x==v10[mij]) return mij+1;
	if(x>v10[mij]) i=mij+1;
	else j=mij-1;
	}
if(x<v10[mij])_nc=mij;
else _nc=mij+1;
return _nc;
}

char* _ulltoa(unsigned long long _n,char *c)  //max 30 caractere
{
c+=31;
*c=0;
do{
	c--;
	*c=_n%10+48;
	_n/=10;
}while(_n);
return c;
}


int main()
{
unsigned long long n,nn,d,m,c,r,l,i,dn;
char s[NMAX+1],x[31],xt[31],*end,*p,*finish,uc[2],*pp;
int ld,dif,lung,lr,carry,pc;
FILE *f=fopen("next.in","r");
freopen("next.out","w",stdout);
fscanf(f,"%s",s);
fscanf(f,"%llu",&d);
l=strlen(s);
finish=s+l;
/*for(i=1;i<=2000000000;i=10*i)
	{ld=nc(i);
	printf("%llu %d\n",i,ld);
	} */
ld=nc(d);
p=s;
lung=ld;
r=0;   /*
if(l<=18){
	n=STRTO(s,&end,10);
	c=n/d;r=n%d;
	if(r) c++;
	m=c*d;
	printf("%llu",m);
	}
else         */
	{
	while(p<finish){
		strncpy(x,p,lung);
		x[lung]='\0';
		p+=lung;
		n=STRTO(x,&end,10);
		r*=v10[lung];
		n+=r;
		r=n%d;
		lr=nc(r);
		lung=ld-lr+1;
		}
	lr=nc(r);
	p=finish-lr;
	strcpy(x,p);
	n=STRTO(x,&end,10);
	//printf("%llu %llu %d\n",r,n,lr);
	if(r)
	{
	n=n+d-r;
	sprintf(x,"%llu",n);
	//pp=_ulltoa(n,x);
	carry=0;
	if(nc(n)>lr){
		strcpy(xt,x+1);
		strcpy(p,xt);
		carry=*x-48;p--;
		while(carry){
			pc=*p-48;
			pc=pc+carry;
			if(pc>9) {pc=pc%10;carry=1;*p=pc+48;p--;}
			else {*p=pc+48;carry=0;}
			}
		}
	else strcpy(p,x);
	}
	printf("%s",s);
	}
return 0;
}