Cod sursa(job #1785763)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 21 octombrie 2016 21:54:45
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.23 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define NPRIM 120
#define MAXD 2000

using namespace std;

void generatePrimes()
{
    for (int maxi = 0x7fffffff, k = 0; k < NPRIM; maxi--) {
        int ok = 1;
        for (int d = 2; ok && 1LL*d*d <= 1LL*maxi; d++)
            if (maxi % d == 0)
                ok = 0;
        if (ok)
            printf("%d, ", maxi), k++;
    }
}
int primes[NPRIM+10] = {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, 2147481179, 2147481173, 2147481151, 2147481143, 2147481139, 2147481071, 2147481053, 2147481031, 2147481019, 2147480989, 2147480971, 2147480969};
int rez[NPRIM+10];
int n, crtVal[30];
char var[30][MAXD];
char expr[100050];

int parse(char *v, int mod)
{
    int sign = 1, nr = 0;
    if (*v == '-') sign = -1, ++v;
    for (; *v >= '0' && *v <= '9'; v++)
        nr = (nr*10LL + *v-'0') % mod;
    nr = (mod + 1LL*sign*nr) % mod;
    return nr;
}

int pos, crtMod, eval(), term(), unit();

int eval()
{
    int nr = term();
    while (expr[pos] == '+' || expr[pos] == '-') {
        int sign = (expr[pos] == '-') ? -1 : 1;
        pos++;
        nr = (1LL*sign*term() + (long long)nr + (long long)crtMod) % crtMod;
    }
    return nr;
}

int term()
{
    int nr = unit();
    while (expr[pos] == '*') {
        pos++;
        nr = (1LL*unit()*nr) % crtMod;
    }
    return nr;
}

int unit()
{
    int nr;
    if (expr[pos] == '(') {
        pos++;
        nr = eval();
        pos++;

    }
    else if (expr[pos] == '[') {
        pos++;
        nr = eval();
        nr = (1LL*nr*nr) % crtMod;
        pos++;
    }
    else if (expr[pos] == '-' || expr[pos] == '+') {
        int ok = expr[pos] == '-';
        pos++;
        nr = eval();
        if (ok)
            nr = (crtMod-nr) % crtMod;
    }
    else {
        nr = crtVal[expr[pos]-'a'];
        pos++;
    }
    return nr;
}

void debug()
{
    for (int i = 0; i < NPRIM; i++)
        printf("%d\n", rez[i]);
}

int rise(int x, int p, int mod)
{
    int rez = 1;
    for (int i = 0; p>>i; i++) {
        if ((p>>i)&1)
            rez = (1LL*rez*x) % mod;
        x = (1LL*x*x) % mod;
    }
    return rez;
}
int sol[MAXD], p[MAXD], temp[MAXD];

void build(int big[], int nr)
{
    memset(big, 0, sizeof sol);
    for (; nr; nr /= 10)
        big[++big[0]] = nr%10;
}

int small(int big[], int mod)
{
    int to = 0;
    for (int i = big[0]; i >= 1; i--)
        to = ((1LL*to*10) + (long long)big[i]) % mod;
    return to;
}

void mult(int in[], int pe[])
{
    int v[MAXD];
    memset(v, 0, sizeof v);
    for (int i = 1, j, t; i <= in[0]; i++)
    {
        for (j = 1, t = 0; j <= pe[0] || t; j++, t /= 10)
            v[i+j-1] = (t += (v[i+j-1] + in[i]*pe[j])) % 10;
        v[0] = max(v[0], i+j-2);
    }
    memcpy(in, v, sizeof v);
}

void add(int in[], int pe[])
{
    int i, t;
    for (i = 1, t = 0; i <= in[0] || i <= pe[0] || t; i++, t/=10)
        in[i] = (t += in[i]+pe[i])%10;
    in[0] = i-1;
}

void sub(int in[], int pe[])
{
    int i, t;
    for (int i = 1, t = 0; i <= in[0]; i++) {
        in[i] = (in[i]-pe[i]-t);
        in[i] += 10*(t = (in[i] < 0));
    }
    while (in[0] > 0 && in[in[0]] == 0) in[0]--;
}

void solveCRT()
{
    /// method 1, incomplete
//    for (int i = 0; i < NPRIM; i++) {
//        verts[i] = 1;
//        for (int j = 0; j < NPRIM; j++)
//            if (i != j)
//                verts[i] = (1LL*verts[i] * primes[j]) % primes[i];
//    }
//    for (int i = 0; i < NPRIM; i++)
//        verts[i] = rise(verts[i], primes[i]-2, primes[i]);
    /// method 2
    build(sol, rez[0]);
    build(p, primes[0]);
    for (int i = 1; i < NPRIM; i++) {
        /// (k1*p1 - k2*p2 = r2-r1)
        int dif = (rez[i] - small(sol, primes[i]));
        while (dif < 0) dif += primes[i];
        int inv = rise(small(p, primes[i]), primes[i]-2, primes[i]);
        int k = (1LL*dif*inv) % primes[i];
        if (k) {
            build(temp, k);
            mult(temp, p);
            add(sol, temp);
        }
        build(temp, primes[i]);
        mult(p, temp);
    }
}

void print(int big[])
{
    for (int i = big[0]; i >= 1; i--)
        printf("%d", big[i]);
}

void afisare()
{
    memset(temp, 0, sizeof temp);
    temp[0] = 1001; temp[temp[0]] = 1;
    if (sol[0] <= 1000)
    {
        sub(temp, sol);
        printf("-");
        print(temp);
    }
    else
    {
        sub(sol, temp);
        print(sol);
    }
}

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

    scanf("%d\n", &n);
    for (int i = 0; i < n; i++)
        gets(var[i]);
    gets(expr);
    for (int i = 0; i < NPRIM; i++) {
        for (int j = 0; j < n; j++)
            crtVal[j] = parse(var[j], primes[i]);
        pos = 0;
        crtMod = primes[i];
        rez[i] = eval();
        rez[i] = (1LL*rez[i] + rise(10, 1000, crtMod)) % crtMod;
    }
    //debug();
    solveCRT();
    afisare();

    return 0;
}