Cod sursa(job #70815)

Utilizator GabiAlb Gabriel Gabi Data 7 iulie 2007 17:49:58
Problema Sarpe Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <string>
using namespace std;

void Inmultire_mic(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 Inmultire(int A[], int B[])
{    
     int i, j, t, C[1001];  
     
     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 Adunare(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 Diferenta(int a[], int b[], int d[])
{
	while ( a[0] > b[0] ) b[++b[0]] = 0;

	int t = 0;
	for ( int i = 1; i <= a[0]; i++ )
	{
		if (  t + a[i] - b[i] >= 0 )
		{
			d[i] = ( t + a[i] - b[i] ) % 10;
			t    = 0;
		}
		else
		{
			d[i] = ( 10 + t + a[i] - b[i] ) % 10;
			t = -1;
		}
	}
	d[0] = a[0];
	while ( d[d[0]] == 0 ) d[0]--;

}

int main()
{
    ifstream fin("sarpe.in");
    ofstream fout("sarpe.out");
    
    string s;
    int nr[1001], nr2[1001], n;
    int a[3] = { 0 }, b[3] = { 0 };
	int aux1[2002] = { 0 }, aux2[1001] = { 0 };
    
    getline(fin, s);
    
    n = s.length();
    
    for (int i = 0; i < n; i++)
        nr[n-i] = s[i] - '0';

    nr[0] = n;
    a[0] = 1;
    a[1] = 1;
    b[0] = 1;
    b[1] = 2;

    memcpy(nr2, nr, sizeof(nr));

    Inmultire_mic(nr, 4);
    Diferenta(nr2, a, aux1);
    Diferenta(nr2, b, aux2);
    Inmultire(aux1, aux2);
    Inmultire_mic(aux1, 2);
    Adunare(nr, aux1);

    for (int i = nr[0]; i >= 1; i--)
        fout << nr[i];

    fout << "\n";

    fin.close();
    fout.close();

    return 0;
}