Cod sursa(job #173862)

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

unsigned long long v10[19]={
1ULL,
10ULL,
100ULL,
1000ULL,
10000ULL,
100000ULL,
1000000ULL,
10000000ULL,
100000000ULL,
1000000000ULL,
10000000000ULL,
100000000000ULL,
1000000000000ULL,
10000000000000ULL,
100000000000000ULL,
1000000000000000ULL,
10000000000000000ULL,
100000000000000000ULL,
1000000000000000000ULL};


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,i,ncc;
char ss[20],s[NMAX+1],/*cs[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);
//strcpy(cs,s);
//i=0;
//while(*s)
//{
//printf("%15s ",s);
l=strlen(s);
finish=s+l;
ld=nc(d);
p=s;
lung=ld;
r=0;

if(l<9){
	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);
	carry=0;
	if(nc(n)>lr){
		strcpy(xt,x+1);
		strcpy(p,xt);
		ncc=strlen(p);
		carry=*x-48;p--;ncc++;
		while(carry){
			pc=*p-48;
			pc=pc+carry;
			if(pc>9)
				{
				if(ncc==l+1) *p=0;
				pc=pc%10;carry=1;*p=pc+48;p--;ncc++;
				if(ncc==l+1) *p='0';
				}
			else {*p=pc+48;carry=0;}
			}
		if(ncc>l) p=s-1;
		else p=s;
		}
	else strcpy(p,x);
	}
	printf("%s",p);
	}
//i++;
//strcpy(s,cs+i);
//}
return 0;
}

/*for(unsigned long i=9;i<=2000000000;i=10*i+9)
	{ld=nc(i);
	printf("%llu %d\n",i,ld);
	} */