Cod sursa(job #502139)

Utilizator SpiderManSimoiu Robert SpiderMan Data 17 noiembrie 2010 20:50:41
Problema A+B Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.09 kb
/*
Colectia personala de operatii pe numere mari - C
Implementate de Robert Simoiu
Incluzand extragerea radacinii patrate cu oricate zecimale
*/

# include <cstring>
# include <cstdio>
# include <cmath>

# define MAX 1000
# define verf( X, i ) ( i <= X[0] ? X[i] : 0 )

void add ( int *A, int *B ) { // A <- A + B
    int i, t = 0;

    for ( i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= 10 )
        A[i] = ( t += verf ( A, i ) + verf ( B, i ) ) % 10 ;
    A[0] = i - 1;
}

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

inline int comp ( int *A, int *B ) { // A ? B , ? == <, >, =
    for ( ; A[0] && !A[A[0]] ; --A[0] ) ; // eliminam zerourile nesemnificative, gen 000001234 -> 1234
    for ( ; B[0] && !B[B[0]] ; --B[0] ) ; // ------------------------ || -----------------------------

    if ( A[0] < B[0] ) return -1;
    else if ( A[0] > B[0] ) return 1;

    for ( int i = A[0]; i > 0; --i )
        if ( A[i] < B[i] ) return -1;
        else if ( A[i] > B[i] ) return 1;

    return 0;
}

void atr ( int *A, int X ) { // A[] <- X
    for ( A[0] = 0; X ; X /= 10 ) {
        A[++A[0]] = X % 10 ;
    }
}

void atrh ( int *A, int *B ) { // A <- B
    for ( int i = 0; i <= B[0]; ++i ) {
        A[i] = B[i] ;
    }
}

void atr0 ( int *A ) { // A[] = 0
    A[0] = 0 ;
}

void mul ( int *A, int B ) { // A[] <- A[] * B
    int i, t = 0;
    for ( i = 1; i <= A[0] || t; ++i, t /= 10 )
        A[i] = ( t += verf ( A, i ) * B ) % 10 ;
    A[0] = i - 1;
}

void mulmare ( int *A, int *B ) { // A <- A * B
    int i, j, t, C[MAX] ;           // C <- A * B

    atr0 ( 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] + verf ( A, i ) * verf ( B, j ) ) % 10;
        if ( i + j - 2 > C[0] ) C[0] = i + j - 2;
    }

    atrh ( A, C ) ;                  // A <- C
}

void Shr ( int *A, int Count) { // A <- A / ( 10 * Count )
    memmove ( &A[1], &A[Count + 1], sizeof(int) * ( A[0] - Count ) );

    A[0] -= Count;
}

void Shl ( int *A, int Count) { // A <- A * ( 10 * Count )
    memmove ( &A[Count + 1], &A[1], sizeof(int) * A[0] );
    memset ( &A[1], 0, sizeof(int) * Count );

    A[0] += Count;
}

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

void impmare ( int *A, int *B, int *C ) { // C <- A / B rest R
    int R[MAX] ;

    R[0] = 0, C[0] = A[0];

    for (int i = A[0]; i ; i--) {
        Shl ( R, 1 ), R[1] = A[i];

        for ( C[i] = 0; comp ( B , R ) != 1 ; ++C[i], sub ( R, B ) ) ;
    }

    for ( ; !C[C[0]] && C[0] > 1 ; --C[0] ) ;
}

int mod ( int *A, int B ) { // return A[] % B
    int i, t = 0;
    for (i = A[0]; i > 0; i--)
        t = ( t * 10 + A[i] ) % B ;
    return t ;
}

void radical_2_cautare_binara ( int *N, int *i ) { // i <- sqrt ( N ) ; doar parte intreaga
    int cnt[MAX], A[MAX];

    cnt[0] = cnt[1] = 1;

    for ( ; comp ( cnt, N ) == -1 ; mul ( cnt, 2 ) ) ; // for (cnt = 1; cnt < N; cnt <<= 1);

    for ( ; ! ( cnt[1] == 0 && cnt[0] == 1 ) ; imp (cnt, 2) ) { //for ( i = 0 ; cnt ; cnt >>= 1 )
        atrh ( A , cnt ) , add ( A , i ), mulmare (A, A) ;

        if ( comp ( A, N ) != 1 )  //  if ( (i + cnt) * (i + cnt) <= N )
            add ( i, cnt );        //  i += cnt ;
    }

}

void radical_2_ca_pe_foaie ( int *A, int *B, int nrzecimale ) { // B <- sqrt ( A )
    int AUX = 0 , i, j = 1;
    int C[MAX], D[MAX], E[MAX], F[MAX], U[MAX] = { 1, 9 }, Z[MAX] = { 1, 1 } ;

    if ( A[0] & 1 ) AUX = A[A[0]], i = A[0] - 1;         // formez prima pereche
    else AUX = A[A[0]] * 10 + A[A[0] - 1], i = A[0] - 2;

    int aux = static_cast < int > ( sqrt ( AUX ) ) ;     // aflu nr. cel mai apropiat de prima pereche

    atr ( B, aux );                                      // atribui rezultatului nr. aflat anterior

    if ( A[0] > 2 ) {

        AUX -= aux * aux;                                    // fac scaderea

        atr ( E, AUX ), Shl ( E, 1 ), atr ( F, A[i] ), add ( E, F ); // E = AUX, E *= 10, E += A[i];
        // adica formez noul numar, adaugand urm. pereche de cate 2 cifre
        Shl ( E, 1 ), atr ( F, A[i - 1] ), add ( E, F );     // E *= 10, E += A[i - 1];
        // la fel, formez noul numar adaugand cea de-a doua cifra
        atrh ( C, E ), atrh ( F, B ), mul ( F, 2 ), atrh ( E, F ); // dublez pe E

        atrh ( D, C ), Shr ( D, 1 ), impmare ( D, E, D );    // aici scap de ultima cifra a nr. si o impart la E

        if ( comp ( D, U ) == 1 ) atr ( D, 9 );              // daca cumva ultima cifra pe care trebuie sa o adaugam la
        // rezultat e > 9, atunci ii atribuim valoarea maxima, 9
        Shl ( E, 1 ), add ( E, D ), mulmare ( E, D );        // E *= 10, E += D, E *= D
        // adica adaug la E cifra D si inmultesc nr. format cu D
        while ( comp(E, C) == 1 )     // daca E > C, adica ca si numarul format din adaugarea perechilor de cate 2 cifre
            sub ( D, Z ), atrh ( F, B ), mul ( F, 2 ),  atrh ( E, F ),  Shl ( E, 1 ),  add ( E, D ), mulmare ( E, D );
        // atunci refac numarul, adica scad o unitate la numarul D si refac operatiile

        sub ( C, E );  // fac scaderea, adica numarul format E il scad din C, care a fost numarul format din ad. celor 2 cifre

        Shl ( B, 1 ), add ( B, D ) ;                         // B *= 10, B += D , adica adaug la rezultat cifra D
    } else {
        atr ( C, AUX - ( aux * aux ) ) ;
    }

    for ( i = i - 2; i > 0 || j <= nrzecimale ; i -= 2 ) {                          // aici merg cu un for care reprezinta pozitia de unde voi adauga cele 2 cifre
        if ( i > 0 ) {
            atr ( E, A[i] ), atr0 ( F ), Shl ( F, 1 ), add ( F, E ) ;     // atribui lui F urmatoarele 2 cifre
            atr ( E, A[i - 1] ), Shl ( F, 1 ), add ( F, E );
        } else {
            ++j, atr0 ( F ) ;
        }
        // iar de aici operatiile se reiau
        Shl ( C, 2 ), add ( C, F ), atrh ( F, B ), mul ( F, 2 ), atrh ( E, F );

        atrh ( D, C ), Shr ( D, 1 ), impmare ( D, E, D );

        if ( comp ( D, U ) == 1 ) atr ( D, 9 ) ;

        Shl ( E, 1 ), add ( E, D ), mulmare ( E, D ) ;

        while ( comp ( E, C ) == 1 )
            sub ( D, Z ), atrh ( F, B ), mul ( F, 2 ),  atrh ( E, F ),  Shl ( E, 1 ),  add ( E, D ), mulmare ( E, D );

        sub ( C, E );

        Shl ( B, 1 ), add ( B, D );
    }
}

void afis_rad ( int *A, int nrzecimale ) { // afisarea radicalului
    for ( int i = A[0] ; i > nrzecimale ; --i )
        printf ( "%d", A[i] ) ;
    printf ( "." ) ;
    for ( int i = nrzecimale ; i ; --i ) {
        printf ( "%d", A[i] ) ;
    }
}

int main ( void ) {
    int a, b ;
    fscanf ( fopen ( "adunare.in", "r" ), "%d %d", &a, &b ) ;
    fprintf ( fopen ( "adunare.out", "w" ), "%d\n", a + b ) ;
}