Cod sursa(job #67946)

Utilizator floringh06Florin Ghesu floringh06 Data 26 iunie 2007 00:24:25
Problema Sarpe Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
using namespace std;

#define MAX_N 3005
#define MAX_D 3005
#define BAZA 10
#define max(a,b) ((a)>(b)?(a):(b))

#include <stdio.h>
#include <string.h>
#include <fstream>

typedef struct 
 {
   int n;
   int x[MAX_D];
 } bignum;  

FILE *fin=fopen("sarpe.in","r"),
     *fout=fopen("sarpe.out","w");
 
bignum n;
bignum sl,p;
 
void read (void)
{
   int i=0;
   char c;
   fscanf(fin,"%c",&c);  
   while (c>=48 && c<=57) {
     n.x[++i]=c-48;
     c='x';
     fscanf(fin,"%c",&c);  
    }
   n.n=i;
   int aux;
   for (i=1; i<=n.n/2; i++)
    { aux=n.x[n.n-i+1]; n.x[n.n-i+1]=n.x[i]; n.x[i]=aux; }  
}     

void multiply (bignum &a, bignum b, bignum c)
{ 
 int t=0,i,j; memset(a.x,0,sizeof(a.x)); a.n=0;
 for (i=1; i<=b.n; i++)
  for (j=1; j<=c.n; j++)
   a.x[i+j-1]+=b.x[i]*c.x[j];
 for (i=1; i<=MAX_D; i++) {
  a.x[i]=(t+=a.x[i])%BAZA; t/=BAZA; }
 for (i=MAX_D; i>=1; i--)
  if (a.x[i]!=0) { a.n=i; break; }
 if (a.n==0) a.n=1;
} 

void multint(bignum &a, int b)
{
  int i,t=0; 
  for (i=1; i<=a.n; i++)
   { a.x[i]=(t+=a.x[i]*b)%BAZA; t/=BAZA; }
  if (t>0) a.x[++a.n]=t;
}

void add(bignum &a, bignum b)
{
  int i,t=0;
  a.n=max(a.n,b.n);
  for (i=1; i<=a.n; i++)
   { a.x[i]=(t+=a.x[i]+b.x[i])%BAZA; t/=BAZA; }
  if (t>0) a.x[++a.n]=t;
}      

void sub(bignum &a,bignum b)  
{  
     int i, t = 0;  
     for (i = 1; i <= a.n; i++)  
              a.x[i] += (t = (a.x[i] -= b.x[i] + t) < 0) * BAZA;  
     for (; a.n > 1 && !a.x[a.n]; a.n--);  
}  


void solve (void)
{
  bignum aux; 
  int i=1;
  i<<=1;
  memset(aux.x, 0, sizeof(aux.x));   
  memcpy(sl.x,n.x,sizeof(n.x));  sl.n=n.n;
  multint(sl,4);
  p.n=1; p.x[1]=2; aux.n=1; aux.x[1]=1;  
  sub(n,aux);
  multiply(p,p,n);
  sub(n,aux);
  multiply(p,p,n);
  add(sl,p);
  return ;
}

void print (void)
{
  int i;   
  fprintf(fout,"%d",sl.x[sl.n]);   
  for (i=sl.n-1; i>=1; i--)
   fprintf(fout,"%d",sl.x[i]);
  fprintf(fout,"\n"); 
}

     
int main()
{
  read();
  solve();
  print();      
  
  fclose(fin);
  fclose(fout);
  return 0;
}