Cod sursa(job #844966)

Utilizator stoicatheoFlirk Navok stoicatheo Data 30 decembrie 2012 01:00:09
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.98 kb
#include <cstdio>
#include <cstring>
 
const int Vmax = 200;
const int Baza = 1000000;
const int Lmax = 100005;
const int NPr = 108;
 
typedef long long (I64);
 
#define out_f "%06d"
 
int N;
int V[32][Vmax], A[32]; char B[32];
 
char Buff[Lmax];
 
char Expr[Lmax], *p; int Mod;
const int Prim[NPr] = {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 P[Vmax], R[Vmax];
 
 
void Sum( 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;
}
 
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]--);
}
 
void Mul( int A[], int B )
{
    if (B == 0)
    {
        memset(A, 0, sizeof(int) * Vmax);
        A[0] = 1;
        return;
    }
 
    int C[Vmax], i; I64 t = 0;
    memset( C, 0, sizeof(C) );
    for (i = 1; i <= A[0] || t; ++i, t /= Baza)
        C[i] = (t += (I64) A[i] * B) % Baza;
    C[0] = i - 1;
    memcpy( A, C, sizeof(C) );
}
  
int Modulo( int A[], int B )
{
    int i; I64 t = 0;
    for (i = A[0]; i >= 1; i--)
        t = (t * Baza + A[i]) % B;
    return t;
}
 
void print( int A[] )
{
    printf("%d", A[ A[0] ]);
    for (int i = A[0] - 1; i >= 1; i--)
        printf("%06d", A[i]);
    printf("\n");
}
 
int Comp( 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;
}
 
int Eval();
int Fact();
int Term();
 
int Euclid( int A, int B, int &X, int &Y )
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }
 
    int X0, Y0;
    int D = Euclid( B, A % B, X0, 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", Buff);
        int poz;
        for (poz = (Buff[0] == '-'); '0' <= Buff[poz] && Buff[poz] <= '9'; poz++);
 
        int put = 1, cif = 0;
        for (poz--; '0' <= Buff[poz] && Buff[poz] <= '9'; poz--)
        {
            cif += put * (Buff[poz] - '0');
            put *= 10;
            if (put == Baza)
                V[i][ ++V[i][0] ] = cif,
                cif = 0, put = 1;
        }
        if (cif)
            V[i][ ++V[i][0] ] = cif;
        if (Buff[0] == '-')
            B[i] = 1;
    }
 
    V[N][ V[N][0] = 1 ] = 1;
    for (int k = 1; k <= 1000; k++)
        Mul( V[N], 10 );
 
    scanf(" %s", Buff);
    sprintf( Expr, "(%s)+%c", Buff, 'a' + N );
 
    memset( P, 0, sizeof(P) ); P[ P[0] = 1 ] = 1;
    memset( R, 0, sizeof( R ) ); R[0] = 1;
    for (int i = 0; i < NPr; ++i)
    {
        p = Expr; Mod = Prim[i];
        for (int j = 0; j <= N; ++j)
        {
            A[j] = Modulo( V[j], Mod );
            if (B[j])
                A[j] = Mod - A[j];
        }
        int Act = Eval();
         
        int D, X0, Y0;
        D = Euclid( Prim[i], Modulo( P, Prim[i] ), X0, Y0 );
         
        int Buff[Vmax];
        memcpy( Buff, P, sizeof(Buff) );
         
        Mul( Buff, (Mod + ((I64) Y0 * ((I64) Act - Modulo( R, Mod )) % Mod)) % Mod );
        Sum( Buff, R );
         
        Mul( P, Prim[i] );
        memcpy( R, Buff, sizeof( R ) );
    }
    if ( Comp( R, V[N] ) < 0 )
    {
        printf("-");
        Sub( V[N], R );
        print(V[N]);
    }
    else
    {
        Sub( R, V[N] );
        print( R );
    }
     
    fclose(stdin);
    fclose(stdout);
    return 0;
}
 
 
int Fact()
{
    if (*p == '+')      
    {
        ++p;
        return Fact();
    }
    if (*p == '-')      
    {
        ++p;
        return Mod - Fact();
    }
    if (*p == '(' || *p == '[')
    {
        int type = (*p == '[');
        ++p;
        int rez = Eval();
        ++p;
 
        if (type)
            return ((I64) rez * rez) % Mod;
        return rez;
    }
 
    ++p;
    return A[ *(p-1) - 'a' ];
}
 
int Term()
{
    int rez = Fact();
    for (; *p == '*'; )
    {
        ++p;
        rez = ((I64) rez * Fact()) % Mod;
    }
    return rez;
}
 
int Eval()
{
    int rez = Term();
    for (; *p == '+' || *p =='-'; )
        if (*p == '+')
        {
            ++p;
            rez = ((I64) rez + Term()) % Mod;
        }
        else
        {
            ++p;
            rez = ((I64) rez - Term() + Mod) % Mod;
        }
    return rez;
}