Cod sursa(job #1050249)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 8 decembrie 2013 13:54:06
Problema Eval Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 8.25 kb
//mlc
//cea mai de rahat parte la un tractor nu e implementarea, e cand ai un bug in 15 kb de sursa ;)

#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <map>
#define prime_count 150
#define ll long long

typedef long long int64;

using namespace std;

map <int, bool> primeMap;
int n, P[prime_count + 1], R[prime_count + 1];

class BigInt {
public:
    static const int MAX_DIGITS = 150;
    static const int BASE = 1000000000;

    int digits[MAX_DIGITS];

    BigInt() {
        memset(digits, 0, sizeof(digits));
        digits[0] = 1;
    }

    BigInt(const string &stringDigits) {
        *this = 0;
        for (int i = 0; i < static_cast<int>(stringDigits.length()); ++i)
            *this = *this * 10 + (stringDigits[i] - '0');
    }

    BigInt(int64 value) {
        memset(digits, 0, sizeof(digits));
        for (; value > 0; value /= BASE)
            digits[++digits[0]] = value % BASE;
        if (digits[0] == 0)
            digits[0] = 1;
    }

    BigInt operator=(const BigInt &other) {
        memcpy(digits, other.digits, sizeof(other.digits));
        return *this;
    }

    BigInt operator=(const int64 value) {
        return *this = BigInt(value);
    }

    BigInt operator+(const BigInt &other) const {
        BigInt result = 0;
        int i; int64 t;
        for (i = 1, t = 0; i <= digits[0] || i <= other.digits[0] || t; ++i, t /= BASE)
            result.digits[i] = (t += (digits[i] + other.digits[i])) % BASE;
        result.digits[0] = i - 1;
        return result;
    }

    BigInt operator+(const int64 value) const {
        return *this + BigInt(value);
    }

    BigInt operator+=(const BigInt &other) {
        return *this = *this + other;
    }

    BigInt operator+=(const int64 value) {
        return *this = *this + value;
    }

    BigInt operator*(const BigInt &other) const {
        BigInt result = 0;
        int i, j; int64 t;
        for (i = 1; i <= digits[0]; ++i) {
            for (j = 1, t = 0; j <= other.digits[0] || t; ++j, t /= BASE)
                result.digits[i + j - 1] = (t += (result.digits[i + j - 1] + 1LL * digits[i] * other.digits[j])) % BASE;
            if (i + j - 2 > result.digits[0])
                result.digits[0] = i + j - 2;
        }
        for (; result.digits[0] > 1 && result.digits[result.digits[0]] == 0; --result.digits[0]);
        return result;
    }

    BigInt operator*(const int64 value) const {
        return *this * BigInt(value);
    }

    BigInt operator*=(const BigInt &other) {
        return *this = *this * other;
    }

    BigInt operator*=(const int64 value) {
        return *this = *this * value;
    }

    BigInt operator-(const BigInt &other) const {
        BigInt result = *this;
        int i; int64 t;
        for (i = 1, t = 0; i <= digits[0]; ++i) {
            result.digits[i] -= (other.digits[i] + t);
            result.digits[i] += ((t = (result.digits[i] < 0 ? 1 : 0)) * BASE);
        }
        for (; result.digits[0] > 1 && result.digits[result.digits[0]] == 0; --result.digits[0]);
        return result;
    }

    BigInt operator-(const int64 value) const {
        return *this - BigInt(value);
    }

    BigInt operator-=(const BigInt &other) {
        return *this = *this - other;
    }

    BigInt operator-=(const int64 value) {
        return *this = *this - value;
    }

    BigInt operator/(const int64 value) const {
        BigInt result = *this;
        int i; int64 t;
        for (i = result.digits[0], t = 0; i > 0 ; --i, t %= value)
            result.digits[i] = (t = (t * BASE + result.digits[i])) / value;
        for (; result.digits[0] > 1 && result.digits[result.digits[0]] == 0; --result.digits[0]);
        return result;
    }

    BigInt operator/=(const int64 value) {
        return *this = *this / value;
    }

    int64 operator%(const int64 value) {
        int64 t = 0;
        for (int i = digits[0]; i > 0; --i)
            t = (1LL * t * BASE + digits[i]) % value;
        return t;
    }

    bool operator<(const BigInt &other) const {
        if (digits[0] != other.digits[0])
            return digits[0] < other.digits[0];
        for (int i = digits[0]; i > 0; --i)
            if (digits[i] != other.digits[i])
                return digits[i] < other.digits[i];
        return false;
    }

    bool operator<=(const BigInt &other) const {
        return !(other < *this);
    }

    bool operator==(const BigInt &other) const {
        return (!(*this < other) && !(other < *this));
    }

    void Print(FILE *stream) const {
        fprintf(stream, "%d", digits[digits[0]]);
        for (int i = digits[0] - 1; i > 0; --i)
            fprintf(stream, "%09d", digits[i]);
    }
};

int sign[30];
char e[100100], tmp[1100];
int modP[30];
int poz, md;
int factor();
int termen();
int eval();
BigInt terms[30];

int factor() {
    if (e[poz] == '+') {
        ++poz;
        return factor();
    }
    if (e[poz] == '-') {
        ++poz;
        return (md - factor()) % md;
    }
    if (e[poz] == '[') {
        ++poz;
        int ret = factor();
        ret = (long long)ret * ret % md;
        ++poz;
        return ret;
    }
    if (e[poz] == '(') {
        ++poz;
        int ret = eval();
        ++poz;
        return ret;
    }
    int ret = modP[(int)e[poz] - 'a' + 1];
    ++poz;
    return ret;
}

int termen() {
    int res = factor();
    while (e[poz] == '*') {
        ++poz;
        res = (long long)res * factor() % md;
    }
    return res;
}

int eval() {
    int res = termen();
    while (e[poz] == '+' || e[poz] == '-') {
        if (e[poz] == '+') {
            ++poz;
            res = ((long long)res + termen()) % md;
        } else {
            ++poz;
            res = ((long long)res - termen() + md) % md;
        }
    }
    return res;
}

inline bool isPrime(int number) {
    if (number % 2 == 0)
        return 0;
    for (int d = 3; d * d <= number; d += 2)
        if (number % d == 0)
            return 0;
    return 1;
}

ll euclid(int A, int B, ll &xx, ll &yy) {
    if (B == 0) {
        xx = 1; yy = 0;
        return A;
    }
    ll xlast, ylast;
    ll gcd = euclid(B, A % B, xlast, ylast);
    xx = ylast;
    yy = xlast - (A / B) * ylast;
    return gcd;
}

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

    srand(time(0));

    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i) {
        gets(tmp);
        if (tmp[0] == '-') {
            sign[i] = -1;
            terms[i] = BigInt(string(tmp + 1));
        } else {
            sign[i] = 1;
            terms[i] = BigInt(string(tmp));
        }
    }
    ++n;
    terms[n] = 1;
    for (int i = 1; i <= 1000; ++i)
        terms[n] *= 10;
    sign[n] = 1;
    gets(e + 1);
    int cnt = strlen(e + 1);
    e[++cnt] = '+'; e[++cnt] = (char)('a' + n - 1);

    for (int i = 1; i <= prime_count; ++i) {
        int curPrime;
        do curPrime = 1000000000 + rand() / 2; while (primeMap[curPrime] || isPrime(curPrime) == 0);
        primeMap[curPrime] = 1;
        P[i] = curPrime;
        for (int j = 1; j <= n; ++j) {
            modP[j] = terms[j] % curPrime;
            if (sign[j] == -1)
                modP[j] = -modP[j] + curPrime;
        }
        poz = 1;
        md = curPrime;
        R[i] = eval();
    }

    BigInt M = P[1], res = R[1];
    for (int i = 2; i <= prime_count; ++i) {
        ll smallM = M % P[i];
        ll smallRes = res % P[i];
        ll rem = R[i] - smallRes;
        if (rem < 0)
            rem += P[i];
        ll xx, yy;
        ll d = euclid(smallM, P[i], xx, yy);
        xx *= (rem / d);
        if (xx < 0)
            xx = P[i] + (xx % P[i]);
        xx %= P[i];
        BigInt nextRes = M;
        nextRes *= xx;
        nextRes += res;
        res = nextRes;
        M *= P[i];
    }

    if (terms[n] <= res ) {
        res -= terms[n];
        res.Print(stdout);
    }
    else {
        printf("-");
        BigInt tmp = terms[n];
        tmp -= res;
        tmp.Print(stdout);
    }

    return 0;
}