Cod sursa(job #527063)

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

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

#define baza 10000
#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);

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