Cod sursa(job #173809)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 8 aprilie 2008 08:30:25
Problema Next Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 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,
1000000000UL,
10000000000UL,
100000000000UL,
1000000000000UL,
10000000000000UL,
100000000000000UL,
1000000000000000UL,
10000000000000000UL,
100000000000000000UL,
1000000000000000000UL}; */

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;
} */

int nc(unsigned long long x)
{
int i;
for(i=1;i<19;i++){
	if(x<v10[i]) break;
	}
return i;
}

int main()
{
unsigned long long n,d,m,c,r,l;
char ss[20],s[NMAX+1],sd[20],x[31],xt[31],*end,*p,*finish;
int ld,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<=15){
	n=STRTO(s,&end,10);
	c=n/d;r=n%d;
	if(r) c++;
	m=c*d;
	printf("%llu",m);
	}
else
	if(ld>l) 	printf("%llu",d);
	else
	{
	while(p<finish){
		strncpy(x,p,lung);
		if(lung>finish-p) lung=finish-p;
		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-ld+1;
	strcpy(x,p);
	n=STRTO(x,&end,10);
   //	printf("%llu %llu %d\n",r,n,lr);
	if(r)
	{
	n=n+d;
	n=n-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;
}