Cod sursa(job #1203090)

Utilizator misinoonisim necula misino Data 30 iunie 2014 17:24:39
Problema Eval Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 9.53 kb
#include<fstream>
#include<cstring>
#include<cstdio>

#define N 30
#define nrp 109
#define L 100100

using namespace std;

ifstream f("eval.in");


int i,n,j,semn[N],MOD,x,valm[N],rez[nrp];

const int prime[nrp] = {0,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};

class numar{
private:
    #define nr *this

    static const int B = 1000000000;
    static const int NN = 200;
    static const int LL = 9;

    int a[NN];

public:
    numar(){
        memset(a,0,sizeof(a));
        a[0] = 1;
    }

    numar(int x){
        memset(a,0,sizeof(a));

        for(; x ; x /= B)
            a[++a[0]] = x % B;

        if(!a[0])
            a[0] = 1;
    }

    numar (string s){
        nr = 0;

        for(int poz = 0 ; poz < s.size() ; ++ poz)
            nr = nr * 10 + (s[poz] - '0');
    }

    inline numar operator=(const numar &b){
        memcpy(a,b.a,sizeof(b.a));
        return *this;
    }

    inline numar operator=(const int x){
        return *this = numar(x);
    }

    inline numar operator +(const numar &b)const{
        numar rez = 0;

        int i;

        long long t;

        for(i = 1 , t = 0 ; i <= a[0] || i <= b.a[0] || t != 0 ; ++ i , t/= B)
            rez.a[i] = (t += 1LL * a[i] + 1LL * b.a[i]) % B ;

        rez.a[0] = i - 1;

        return rez;
    }

    inline numar operator +(const int x){
        return *this = *this + numar(x);
    }

    inline numar operator +=(const numar &b){
        return *this = *this + b;
    }

    inline numar operator +=(const int x){
        return *this = *this + numar(x);
    }

    inline numar operator -(const numar &b)const{
        numar rez = *this;

        int i,t;

        for(i = 1 , t = 0 ; i <= a[0] ; ++ i)
        {
            rez.a[i] = rez.a[i] - b.a[i] - t;
            rez.a[i] += ((t = (rez.a[i] < 0)?1:0) * B);
        }

        for(;rez.a[0] > 1 && rez.a[rez.a[0]] == 0 ; -- rez.a[0]);

        return rez;
    }

    inline numar operator -(const int x){
        return *this = *this - numar(x);
    }

    inline numar operator -=(const numar & b){
        return *this = *this - b;
    }

    inline numar operator -=(const int x){
        return *this = *this - numar(x);
    }

    inline numar operator *(const numar &b)const{
        numar rez = 0;

        int i,j;
        long long t;

        for(i = 1 ; i <= a[0] ; ++ i)
        {
            for(j = 1 , t = 0 ; j <= b.a[0] || t != 0; ++ j , t /= B)
                rez.a[i + j - 1] = (t += 1LL * rez.a[i + j - 1] + 1LL * a[i] * b.a[j]) % B;

            if(rez.a[0] < i + j - 2)
                rez.a[0] = i + j - 2;
        }

        return rez;
    }

    inline numar operator *(const int x){
        return *this = *this * numar(x);
    }

    inline numar operator *=(const numar &b){
        return *this = *this * b;
    }

    inline numar operator *=(const int x){
        return *this *= numar(x);
    }

    inline numar operator /(const int x)const{
        numar rez = *this;

        int i , t;

        for(i = rez.a[0] , t = 0 ; i ; -- i , t %= x)
            rez.a[i] = (t = 1LL * t * B + rez.a[i]) / x;

        for(;rez.a[0] > 1 && rez.a[rez.a[0]] == 0 ; -- rez.a[0]);

        return rez;
    }

    inline numar operator /=(const int x){
        return *this = *this / x;
    }

    inline int operator %(const int x){
        numar rez = *this;

        int i ;
        long long t;

        for(i = rez.a[0] , t = 0 ; i ; -- i , t %= x)
            rez.a[i] = (t = 1LL * t * B + rez.a[i]) / x;

        return t;
    }

    inline int operator %=(const int x){
        return *this % x;
    }

    inline bool operator ==(const numar &b)const{
        if(a[0] != b.a[0])
            return false;

        for(int i = 1 ; i <= a[0] ; ++ i)
            if(a[i] != b.a[i])
            return false;

        return true;
    }

    bool operator ==(const int x)const{
        return *this == numar(x);
    }

    inline bool operator <(const numar &b)const{
        if(a[0] != b.a[0])
            return a[0] < b.a[0];
        for(int i = a[0] ; i ; -- i)
            if(a[i] != b.a[i])
            return a[i] < b.a[i];

        return false;
    }

    inline bool operator <(const int x)const{
        return *this < numar(x);
    }

    inline bool operator >(const numar &b)const{
        if(a[0] != b.a[0])
            return a[0] > b.a[0];
        for(int i = a[0] ; i ; -- i)
            if(a[i] != b.a[i])
            return a[i] > b.a[i];

        return false;
    }

    inline bool operator > (const int x)const{
        return *this > numar(x);
    }

    inline bool operator <=(const numar &b)const{
        return (*this < b || *this == b);
    }

    inline bool operator <=(const int x)const{
        return *this <= numar(x);
    }

    inline bool operator >=(const numar &b)const{
        return (*this > b || *this == b);
    }

    inline bool operator >=(const int x)const{
        return *this >= numar(x);
    }

    inline bool operator !=(const numar &b)const{
        return !(*this == b);
    }

    inline bool operator !=(const int x)const{
        return *this != numar(x);
    }

    inline void afis()const{
        printf("%d" , a[a[0]]);

        for(int i = a[0] - 1 ; i ; -- i)
            printf("%09d",a[i]);
    }
};

inline int putere(int n,int p){
    int sol = 1;

    while(p > 0)
    {
        if(p & 1)
        {
            -- p;
            sol = (1LL * sol * n) % MOD;
        }
        else
        {
            p >>= 1;
            n = (1LL * n * n) % MOD;
        }
    }

    return sol;
}

numar val[N],sol,prod;

char *p,expresie[L];

string s,ex;

inline int exp();
inline int termen();
inline int factor();

inline int factor(){
    if(*p == '('){
        ++ p;

        int rez = exp();

        ++ p;

        return rez;
    }

    if(*p == '['){
        ++ p;

        int rez = exp();

        ++ p;

        return rez;
    }

    if(*p == '+'){
        ++ p;

        return exp();
    }

    if(*p == '-'){
        ++ p;
        return (MOD - exp()) % MOD;
    }


    int rez =  valm[*p - 'a' + 1] % MOD;

    ++ p;

    return rez;
}

inline int termen(){
    int rez = factor();

    while(*p == '*')
    {
        ++ p;

        rez =(1LL * rez * factor()) % MOD;
    }

    return rez;
}

inline int exp(){
    int rez = termen();

    while(*p == '+' || *p == '-')
        if(*p == '+')
    {
        ++ p;

        rez = (1LL * rez + termen()) % MOD;
    }
    else
    {
        ++ p;

        rez = (1LL * rez + MOD - termen()) % MOD;
    }

    return rez;
}

int main()
{
    freopen("eval.out","w",stdout);

    f >> n;

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> s;

        if(s[0] == '-')
        {
            semn[i] = -1;
            string ss;

            for(int poz = 1 ; poz < s.size() ; ++ poz)
                ss.push_back(s[poz]);

            s = ss;
        }
        else
        {
            semn[i] = 1;
        }

        val[i] = numar(s);
    }

    f >> ex;

    ex = ex + "+" + (char)('a' + 26);

    for(i = 0 ; i < ex.size() ; ++ i)
        expresie[i] = ex[i];

    expresie[i] = 0;
    semn[27] = 1;
    val[27] =1;

    for(i = 1 ; i <= 1000 ; ++ i)
        val[27] = val[27] * 10;

    for(i = 1 ; i < nrp ; ++ i)
    {
        p = expresie;

        MOD = prime[i];

        for(j = 1 ; j <= 27 ; ++ j)
        {
            valm[j] = val[j] % MOD;

            if(semn[j] == -1)
                valm[j] = MOD - valm[j];
        }
        rez[i] = exp();
    }

    sol = rez[1];
    prod = prime[1];

    for(i = 2 ; i < nrp ; ++ i)
    {
        MOD = prime[i];

        x = rez[i]  - (sol % MOD);

        if(x < 0)
            x += MOD;
        x = (1LL * x * putere(prod % MOD , MOD - 2)) % MOD;

        if(x)
        {
            numar k = prod;

            sol += k* x;
        }
        prod *= prime[i];
    }
    numar put = 1;

    for(i = 1 ; i <= 125 ; ++ i)
        put *= 100000000;

    if(sol < put)
    {
        printf("-");
        sol = put - sol;
    }
    else
        sol -= put;

    sol.afis();

    return 0;
}