Cod sursa(job #68086)

Utilizator swift90Ionut Bogdanescu swift90 Data 26 iunie 2007 13:57:15
Problema Sarpe Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
#include<string.h>
int nr[1005],sum[3005],aux[3005],s[3005];
char v[1005];
int main(){
	freopen("sarpe.in","r",stdin);
	freopen("sarpe.out","w",stdout);
	int i,j,t;
	
	scanf("%s",v);
	s[0]=nr[0]=strlen(v);
	for(i=1;i<=nr[0];i++)
		s[i]=nr[i]=v[nr[0]-i]-'0';
	
	if(nr[0]==1){
		i=nr[1];
		if(i==1)
			printf("1\n");
		else{
			j=4*i;
			j+=2*(i-1)*(i-2);
			printf("%d\n",j);
		}
		return 0;
	}
	
	for (i = 1,t=0; i <= s[0] || t; i++, t /= 10)
		s[i] = (t += s[i] *4) % 10;
	s[0] = i - 1;
	
	for(i=0;i<=s[0];i++)
		sum[i]=s[i];
	
	aux[0]=aux[1]=1;
	t=0;
	for (i = 1; i <= nr[0]; i++)
		nr[i] += (t = (nr[i] -= aux[i] + t) < 0) * 10;
	for (; nr[0] > 1 && !nr[nr[0]]; nr[0]--);
	
	memset(s,0,sizeof(s));
	
	for(i=0;i<=nr[0];i++)
		s[i]=nr[i];
	
	t=0;
	for (i = 1; i <= s[0]; i++)
		s[i] += (t = (s[i] -= aux[i] + t) < 0) * 10;
	for (;s[0] > 1 && !s[s[0]]; s[0]--);
	
	
	memset(aux, 0, sizeof(aux));
	for (i = 1; i <= nr[0]; i++){
		for (t=0, j=1; j <= s[0] || t; j++, t/=10)
			aux[i+j-1]=(t+=aux[i+j-1]+nr[i]*s[j])%10;
		if (i + j - 2 > aux[0]) aux[0] = i + j - 2;
	}
	
	t=0;
	for (i = 1; i <= aux[0] || t; i++, t /= 10)
		aux[i] = (t += aux[i] * 2) % 10;
	aux[0] = i - 1;
	
	for (i=1,t=0; i<=sum[0] || i<=aux[0] || t; i++, t/=10)
		sum[i] = (t += sum[i] + aux[i]) % 10;
	sum[0] = i - 1;
	
	for(i=sum[0];i>0;i--)
		printf("%d",sum[i]);
	printf("\n");
	
	return 0;
}