Cod sursa(job #527065)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 30 ianuarie 2011 15:59:06
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <cstring>

#define file_in "sarpe.in"
#define file_out "sarpe.out"

#define baza 10
#define nmax 10000

int N;
int A[nmax];
int B[nmax];
int C[nmax];
int D[nmax];
int Q[nmax];


void add(int A[], int B[]){
	
	int i,t=0;
	
	for (i=1;i<=A[0] || i<=B[0] || t;++i,t/=baza)
		 A[i]=(t+=A[i]+B[i])%baza;
	A[0]=i-1;
}

void mul_mic(int A[], int B){
	
	int i,t=0;
	
	for (i=1;i<=A[0] || t;++i,t/=baza)
		 A[i]=(t+=A[i]*B)%baza;
	A[0]=i-1;
}

void mul_mare(int A[], int B[])
{
      int i,j,t,C[nmax];
      memset(C,0,sizeof(C));
      for (i=1;i<=A[0];i++)
      {
              for (t=0,j=1;j<=B[0] || t; j++,t/=baza)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%baza;
              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]-=((i<=B[0])?B[i]:0)+t)<0)*baza;
	for (;A[0]>1 && !A[A[0]];A[0]--); 
}

	

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	char s[nmax];         
     int l,i;
    scanf("%s",s);         
    l=strlen(s);         
    for (i=1;i<=l;++i)         
    {         
        ++A[0];         
            if (l-i>=0)         
                A[A[0]]=A[A[0]]*10+s[l-i]-'0';        
           
    }         

	if (A[1]==1 && A[0]==1){
		printf("2\n");
		return 0;
	}
	
	memcpy(B,A,sizeof(A));
	memcpy(C,A,sizeof(A));
	D[0]=1;
	D[1]=4;
	mul_mare(A,B);
	mul_mic(A,2);
	mul_mic(C,2);
	sub(A,C);
	add(A,D);
	
	//printf("%d", A[A[0]]);
	for (int i=A[0];i>=1;--i)
		 printf("%d", A[i]);
	
	return 0;
	
}