Cod sursa(job #88596)

Utilizator slayer4uVictor Popescu slayer4u Data 3 octombrie 2007 10:34:38
Problema Sarpe Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>
#include<string.h>
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 (i=n[0];i>=1;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 (i=1;i<=n[0];i++)
		printf("%d",n[i]);
	printf("\n");
	return 0;
}