Cod sursa(job #1777320)

Utilizator silkMarin Dragos silk Data 12 octombrie 2016 11:44:36
Problema Sarpe Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <cstring>
#define NMax 2005

char s[NMax+1];
int F[NMax+1];
int N[NMax+1];
int A[NMax+1];
int B[NMax+1];
int T[3];

void mul_ct(int * X, int P)
{
    int i,t=0;
    for(i = 1; i <= X[0] || t; ++i, t/=10)
    X[i] = ( t = X[i] * P + t ) % 10;

    X[0] = i-1;
}

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] + t ) % 10;

    A[0] = i-1;
}

void sub(int * A, int * B)
{
      int i, t = 0;
      for (i = 1; i <= A[0]; i++) {
              A[i] -= ((i <= B[0]) ? B[i] : 0) + t;
              A[i] += (t = A[i] < 0) * 10;
      }
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

void mul(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/=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));
}

int main(){
    freopen("sarpe.in","r",stdin);
    freopen("sarpe.out","w",stdout);

    int i,lg;

    fgets(s, NMax-1, stdin);
    lg = strlen(s);
    if( s[lg-1] == '\n' ) --lg;

    A[0] = B[0] = N[0] = lg;
    for(i = 1; i <= lg; ++i) A[i] = B[i] = N[i] = s[lg-i] - '0';
    if( N[0] == 1 && N[1] == 1 ) { printf("1\n"); return 0; }

    mul_ct(N,4);
    T[0] = 1;
    T[1] = 1; sub(A,T);
    T[1] = 2; sub(B,T);

    mul_ct(A,2);
    mul(A,B);
    add(N,A);

    for(i = N[0]; i >= 1; --i ) printf("%d", N[i] );



return 0;
}