Cod sursa(job #1015645)

Utilizator enedumitruene dumitru enedumitru Data 24 octombrie 2013 21:52:04
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<cstdio>
#include<cstring>
using namespace std;
int n[100001],n1[100001],n2[100001],unu[100001],doi[100001],i;
char s[1001];
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 mul(int A[], int B[])
{   int i,j,t,C[100001];
	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 mulmic(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 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","rt",stdin); freopen ("sarpe.out","wt",stdout);
    scanf("%s",s);
    if(s[0]=='1' && s[1]==0) {printf("2\n");return 0;}
    n[0]=n1[0]=n2[0]=strlen(s);
    for(int i=n[0]; i; i--) n1[i]=n2[i]=n[i]=s[n[0]-i]-'0';
    unu[0]=unu[1]=1;
    doi[0]=1,doi[1]=2;
    mulmic(n,4);
    sub(n1,unu);
    sub(n2,doi);
    mul(n1,n2);
    mulmic(n1,2);
    add(n,n1);
    for(int i=n[0]; i ;i--) printf("%d",n[i]);
    printf("\n");
    return 0;
}