Cod sursa(job #68316)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 iunie 2007 15:47:09
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <string>

#define maxn 510
#define maxx 1010
#define baza 10000

int a[maxn],b[maxn];
char v[maxx];

void print(int a[])
{
     printf("%d",a[a[0]]);
     int i;
     
     for (i=a[0]-1;i>0;i--) printf("%04d",a[i]);
     printf("\n");
}

void read(int a[])
{
     fgets(v,maxx,stdin);
     
     int i,l=strlen(v)-2,zece;
     
     for (i=l;i>=0;i--)
     {
         if (i%4==l%4)
         {
             a[0]++;
             zece=1;
         }
         a[a[0]]+=(v[i]-'0')*zece;
         zece*=10;
     }
}

void scade(int b[],int a[],int x)
{
     int t=x,i;

     for (i=1;i<=a[0] || t>0;i++)
     {     
           if (a[i]-t<0) 
           {
               b[i]=a[i]-t+baza;
               t=1;
           }
           else {
                     b[i]=a[i]-t;
                     t=0;
                }
     }
     
     b[0]=i-1;
}

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

void mult(int a[],int b[],int c[])
{
     int s[maxn],d[maxn];
     int i,j,t;
     
     memset(s,0,sizeof(s));
     for (i=1;i<=b[0];i++)
     {
         t=0;
         memset(d,0,sizeof(d));
         for (j=1;j<=c[0] || t>0;j++) 
         {
             d[j+i-1]=(b[i]*c[j]+t) % baza;
             t=(b[i]*c[j]+t) / baza;
         }
         
         d[0]=i+j-2;
         add(s,d);
     }
     
     memcpy(a,s,sizeof(s));
}

void multx(int a[],int x)
{
     int i,t=0,aux;
     
     for (i=1;i<=a[0] || t>0;i++)
     {
         aux=(a[i]*x+t) % baza;
         t=(a[i]*x+t) / baza;
         a[i]=aux;
     }
     
     a[0]=i-1;
}

int main()
{
    freopen("sarpe.in","r",stdin);
    freopen("sarpe.out","w",stdout);
    
    read(a);
    
    if ((a[0]==1) && (a[1]==1)) 
    {
          printf("2\n");
          return 0;
    }
    
    scade(b,a,1);
    mult(a,a,b);
    memset(b,0,sizeof(b));
    b[1]=2;b[0]=1;
    add(a,b);
    multx(a,2);
    print(a);
        
    return 0;
}