Cod sursa(job #74053)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 iulie 2007 18:04:28
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int n[100000], m[100000], p[100000], s[100000], i, a, nr, x, aux;
char c;
void add(int A[], int B[])   
{   
	int i, t = 0;   
	for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)   
		A[i] = (t += A[i] + B[i]) % 10;   
	A[0] = i - 1;   
}   
void mul1(int A[], int B)   
{   
	int i, t = 0;   
	for (i = 1; i <= A[0] || t; i++, t /= 10)   
		A[i] = (t += A[i] * B) % 10;   
	A[0] = i - 1;   
}   
void mul2(int A[], int B[])   
{   
	int i, j, t, C[100000];   
	memset(C, 0, sizeof(C));   
	for (i = 1; i <= A[0]; i++)   
	{   
		for (t=0, j=1; j <= B[0] || t; j++, t/=10)   
			C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;   
		if (i + j - 2 > C[0]) C[0] = i + j - 2;   
	}   
	memcpy(A, C, sizeof(C));   
}
void sub(int A[], int B[])   
{   
	int i, t = 0;   
	for (i = 1; i <= A[0]; i++)   
		A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;   
	for (; A[0] > 1 && !A[A[0]]; A[0]--);   
}   

int main()
{
	freopen("sarpe.in","r",stdin);
	freopen("sarpe.out","w",stdout);
	nr = 0;
	x = scanf("%c", &c);
	while (x != EOF){
		if (isdigit(c))
			n[++nr] = c-'0';
		x = scanf("%c", &c);
	}
	n[0] = nr;
	if (n[0] == 1 && n[1] == 1){
		printf("2\n");
		return 0;
	}
	for (i=1; i<=(n[0]+1)/2; i++){
		aux = n[i];
		n[i] = n[nr-i+1];
		n[nr-i+1] = aux;
		m[i] = n[i];
		m[nr-i+1] = n[nr-i+1];
		p[i] = n[i];
		p[nr-i+1] = n[nr-i+1];
	}
	m[0] = n[0];
	p[0] = n[0];
	a = 4;
	mul1(n, a);
	s[0] = 1;
	s[1] = 1;
	sub(m, s);
	s[1] = 2;
	sub(p, s);
	mul2(m, p);
	a = 2;
	mul1(m, a);
	add(n, m);
	for (i=n[0]; i>0; i--)
		printf("%d", n[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}