Cod sursa(job #1700002)

Utilizator sucureiSucureiRobert sucurei Data 9 mai 2016 08:04:42
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.54 kb
#include <stdio.h>
#include <string.h>

#define MAXVL 200
#define BAZA 1000000
#define OUTPUT_FORMAT "%06d"
#define MAXL 100005
#define NRPR 108

int N;
int val[32][MAXVL], valMod[32]; char valNeg[32];

char tmp[MAXL];

char expr[MAXL], *p; int MOD;
const int PRIM[NRPR] = {2147483647, 2147483629, 2147483587, 2147483579, 2147483563, 2147483549, 2147483543, 2147483497, 2147483489, 2147483477, 2147483423, 2147483399, 2147483353, 2147483323, 2147483269, 2147483249, 2147483237, 2147483179, 2147483171, 2147483137, 2147483123, 2147483077, 2147483069, 2147483059, 2147483053, 2147483033, 2147483029, 2147482951, 2147482949, 2147482943, 2147482937, 2147482921, 2147482877, 2147482873, 2147482867, 2147482859, 2147482819, 2147482817, 2147482811, 2147482801, 2147482763, 2147482739, 2147482697, 2147482693, 2147482681, 2147482663, 2147482661, 2147482621, 2147482591, 2147482583, 2147482577, 2147482507, 2147482501, 2147482481, 2147482417, 2147482409, 2147482367, 2147482361, 2147482349, 2147482343, 2147482327, 2147482291, 2147482273, 2147482237, 2147482231, 2147482223, 2147482121, 2147482093, 2147482091, 2147482081, 2147482063, 2147482021, 2147481997, 2147481967, 2147481949, 2147481937, 2147481907, 2147481901, 2147481899, 2147481893, 2147481883, 2147481863, 2147481827, 2147481811, 2147481797, 2147481793, 2147481673, 2147481629, 2147481571, 2147481563, 2147481529, 2147481509, 2147481499, 2147481491, 2147481487, 2147481373, 2147481367, 2147481359, 2147481353, 2147481337, 2147481317, 2147481311, 2147481283, 2147481269, 2147481263, 2147481247, 2147481209, 2147481199};

int prod[MAXVL], rest[MAXVL];

//Numere mari
inline void add( int A[], int B[] )
{
    int i, t = 0;
    for (i = 1; i <= A[0] || i <= B[0] || t; i++, t /= BAZA)
        A[i] = (t += A[i] + B[i]) % BAZA;
    A[0] = i - 1;
}

inline void sub( int A[], int B[] )
{
    int i, t = 0;

    for (i = 1; i <= A[0]; i++)
    {
        A[i] -= B[i] + t;
        t = (A[i] < 0);
        A[i] += t * BAZA;
    }

    for (; A[0] && !A[A[0]]; A[0]--);
}

inline void mul( int A[], int B )
{
    if (B == 0)
    {
        memset(A, 0, sizeof(int) * MAXVL);
        A[0] = 1;
        return;
    }

    int C[MAXVL], i; long long t = 0;
    memset( C, 0, sizeof(C) );
    for (i = 1; i <= A[0] || t; i++, t /= BAZA)
        C[i] = (t += (long long)A[i] * B) % BAZA;
    C[0] = i - 1;
    memcpy( A, C, sizeof(C) );
}

inline int mod( int A[], int B )
{
    int i; long long t = 0;
    for (i = A[0]; i >= 1; i--)
        t = (t * BAZA + A[i]) % B;
    return t;
}

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

inline int cmp( int A[], int B[] )
{
    if (A[0] < B[0])
        return -1;
    if (A[0] > B[0])
        return 1;

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

//Evaluare expresii
int expresie();
int factor()
{
    if (*p == '+')      //operator unar
    {
        p++;
        return factor();
    }
    if (*p == '-')      //operator unar
    {
        p++;
        return MOD - factor();
    }
    if (*p == '(' || *p == '[')
    {
        int type = (*p == '[');
        p++;
        int rez = expresie();
        p++;

        if (type)
            return ((long long)rez * rez) % MOD;
        return rez;
    }

    int rez = valMod[ *p - 'a' ]; p++;
    return rez;
}

int termen()
{
    int rez = factor();
    for (; *p == '*'; )
    {
        p++;
        rez = ((long long)rez * factor()) % MOD;
    }
    return rez;
}

int expresie()
{
    int rez = termen();
    for (; *p == '+' || *p =='-'; )
        if (*p == '+')
        {
            p++;
            rez = ((long long)rez + termen()) % MOD;
        }
        else
        {
            p++;
            rez = ((long long)rez - termen() + MOD) % MOD;
        }
    return rez;
}

//GCD extins
int gcd( int A, int B, int &X, int &Y )
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int X0, Y0;
    int D = gcd( B, A % B, X0, Y0 );
    //D == B * X0 + (A % B) * Y0
    //D == B * X0 + (A - [A / B] * B) * Y0
    //D == B * X0 + A * Y0 - B * [A / B] * Y0

    X = Y0;
    Y = X0 - (A / B) * Y0;
    return D;
}

int main()
{
    freopen("eval.in", "rt", stdin);
    freopen("eval.out", "wt", stdout);

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf(" %s", tmp);
        int poz;
        for (poz = (tmp[0] == '-'); '0' <= tmp[poz] && tmp[poz] <= '9'; poz++);

        int put = 1, cif = 0;
        for (poz--; '0' <= tmp[poz] && tmp[poz] <= '9'; poz--)
        {
            cif += put * (tmp[poz] - '0');
            put *= 10;
            if (put == BAZA)
                val[i][ ++val[i][0] ] = cif,
                cif = 0, put = 1;
        }
        if (cif)
            val[i][ ++val[i][0] ] = cif;
        if (tmp[0] == '-')
            valNeg[i] = 1;
    }

    //adun 10^1000 la rezultat ca sa nu dea negativ
    val[N][ val[N][0] = 1 ] = 1;
    for (int k = 1; k <= 1000; k++)
        mul( val[N], 10 );

    scanf(" %s", tmp);
    sprintf( expr, "(%s)+%c", tmp, 'a' + N );

    memset( prod, 0, sizeof(prod) ); prod[ prod[0] = 1 ] = 1;
    memset( rest, 0, sizeof(rest) ); rest[0] = 1;
    for (int i = 0; i < NRPR; i++)
    {
        p = expr; MOD = PRIM[i];
        for (int j = 0; j <= N; j++)
        {
            valMod[j] = mod( val[j], MOD );
            if (valNeg[j])
                valMod[j] = MOD - valMod[j];
        }
        int curRest = expresie();

        //Pentru 2 numere (X1, X2) prime intre ele tb sa rezolv sistemul
        //N === R1 (mod X1)
        //N === R2 (mod X2)

        //X1 * C1 + R1 == X2 * C2 + R2
        //X1 * C1 - X2 * C2 == R2 - R1

        int D, X0, Y0;
        D = gcd( PRIM[i], mod( prod, PRIM[i] ), X0, Y0 );
        //X = Y0;
        //Y = (prod / PRIM[i]) * Y0 - X0;

        int tmp[MAXVL];
        memcpy( tmp, prod, sizeof(tmp) );

        mul( tmp, (MOD + ((long long)Y0 * ((long long)curRest - mod( rest, MOD )) % MOD)) % MOD );
        add( tmp, rest );

        mul( prod, PRIM[i] );
        memcpy( rest, tmp, sizeof(rest) );
    }
    if ( cmp( rest, val[N] ) < 0 )
    {
        printf("-");
        sub( val[N], rest );
        print(val[N]);
    }
    else
    {
        sub( rest, val[N] );
        print(rest);
    }

    return 0;
}