Cod sursa(job #321653)

Utilizator Abi79Iordache Albert Abi79 Data 6 iunie 2009 20:20:35
Problema Next Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<stdio.h>
#include<string.h>
FILE *in=fopen("next.in","r"),*out=fopen("next.out","w");

int n[1000001],d[17],aux[1000001],r[1000001];;
char s1[1000001],s2[18];

void init(char S1[],int V1[],char S2[],int V2[])
{
	long int i;
	
	for(i=1;i<=V1[0];i++)
	{
		V1[i]=(int)S1[V1[0]-i]-48;
		V2[i]=(int)S2[V2[0]-i]-48;
	}
	
	while(i<=V2[0])
	{
		V2[i]=(int)S2[V2[0]-i]-48;
		i++;
	}
}


void afis()
{
	long int i;
	for(i=n[0];i;)
	{
		fprintf(out,"%d",n[i--]);
	}
}


void Shl2()
{
	long int j;

	for (j=r[0];j;j--) r[j+1]=r[j];  

	for (j=1;j<=1;) r[j++]=0;  

	r[0]+=1;  
}  


int compara()
{
	long int j;
	
	while(d[0] && !d[d[0]]) d[0]--;
	while(r[0] && !r[r[0]]) r[0]--;
	
	if(d[0]<r[0])
		return -1;
	else if (d[0]>r[0])
		return 1;
	
	for (j = d[0];j>0;j--)
	{
		if(d[j]<r[j]) return -1;
		else if (d[j]>r[j]) return 1;
	}
	
	return 0;
}


void scadere(int a[],int b[])  
{
	int T=0;
	long int j;
   
	for (j=b[0]+1;j<=a[0];) b[j++]=0;  
	for (j=1;j<=a[0];j++)  
	{
		a[j]=a[j]-(b[j]+T); 
		if (a[j]<0) T=1; else T=0; 
		if (T) a[j]+=10;
	}
	while (!a[a[0]]) a[0]--;  
}  


void impartire()
{
	long int i;
	r[0]=0;
	
	for (i=n[0];i;i--)
	{
		Shl2(); /*muta tot vectorul r cu 1 mai la dreapta*/
		
		r[1]=n[i];
		
		while (compara()!=1) /*compara d cu r*/
			scadere(r,d); /*r-=d*/
	}
	if(r[0]>0) 
	{
		aux[0]=r[0];
		for(i=1;i<=r[0];i++)
			aux[i]=r[i];
	}
}


void adunare()
{ 
	int T=0;
	long int i;
	
	for(i=d[0]+1;i<=n[0];) d[i++]=0;
	
	for(i=1;i<=n[0];i++)
	{
		n[i]=n[i]+d[i]+T;
		T=n[i]/10;
		n[i]=n[i]%10;
	}
	
	if (T) n[++n[0]]=T;
}


int main()
{	
	fgets(s1,1000001,in);
	fgets(s2,18,in);
	n[0]=strlen(s1)-1; d[0]=strlen(s2);
	
	if(n[0]>d[0])
		init(s2,d,s1,n);
	else
	{
		fprintf(out, "%s",s2);
		fclose(out);
		return 0;
	}
	
	impartire(); /* aux = n%d */
	
	adunare(); /* n = n + d */
	
	scadere(n,aux); /* n = n - aux */
	
	afis();	
	
	fclose(out);
	
	return 0;
}