Cod sursa(job #996348)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 11 septembrie 2013 17:47:55
Problema Eval Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 9.99 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long int64;

const int MAX_LENGTH = 100005;
const int SIGMA = 27;
const int PRIMES_COUNT = 108;
const int PRIMES[PRIMES_COUNT] = {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 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]);
    }
};

BigInt Variables[SIGMA], MaxValue, Solution;
int Signs[SIGMA], VariablesMod[SIGMA], Mod, SolutionSign;
char Expression[MAX_LENGTH], *Pointer;

int64 ExtendedGCD(const int64 a, const int64 b, int64 &x, int64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64 d, x0, y0;
    d = ExtendedGCD(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

BigInt SolveSystem(const int n, const vector<int> &primes, const vector<int> &remainders) {
    BigInt solution = remainders[0], M = primes[0];
    for (int i = 1; i < n; ++i) {
        int64 A = M % primes[i], B = (remainders[i] - (solution % primes[i]) + primes[i]) % primes[i];
        int64 x, y;
        int64 d = ExtendedGCD(A, primes[i], x, y);
        x = x * (B / d);
        if (x < 0)
            x = primes[i] + (x % primes[i]);
        x %= primes[i];
        solution += M * x;
        M *= primes[i];
    }
    return solution;
}

int ComputeFactor();
int ComputeTerm();
int ComputeExpression();

int ComputeFactor() {
    if (*Pointer == '+') {
        ++Pointer;
        return ComputeFactor();
    }
    if (*Pointer == '-') {
        ++Pointer;
        return (-ComputeFactor() + Mod) % Mod;
    }
    if (*Pointer == '(') {
        ++Pointer;
        int result = ComputeExpression();
        ++Pointer;
        return result;
    }
    if (*Pointer == '[') {
        ++Pointer;
        int result = ComputeExpression();
        ++Pointer;
        return (1LL * result * result) % Mod;
    }
    int result = VariablesMod[static_cast<int>(*Pointer - 'a')];
    ++Pointer;
    return result;
}

int ComputeTerm() {
    int result = ComputeFactor();
    while (*Pointer == '*') {
        ++Pointer;
        result = (1LL * result * ComputeFactor()) % Mod;
    }
    return result;
}

int ComputeExpression() {
    int result = ComputeTerm();
    while (*Pointer == '+' || *Pointer == '-') {
        if (*Pointer == '+') {
            ++Pointer;
            result = (1LL * result + ComputeTerm()) % Mod;
        } else {
            ++Pointer;
            result = (1LL * result - ComputeTerm() + Mod) % Mod;
        }
    }
    return result;
}

void Solve() {
    int n = PRIMES_COUNT;
    vector<int> remainders(n), primes(n);
    for (int i = 0; i < n; ++i) {
        primes[i] = Mod = PRIMES[i];
        for (int j = 0; j < SIGMA; ++j) {
            VariablesMod[j] = Variables[j] % Mod;
            if (Signs[j] == -1)
                VariablesMod[j] = Mod - VariablesMod[j];
        }
        Pointer = Expression;
        remainders[i] = ComputeExpression();
    }
    Solution = SolveSystem(n, primes, remainders);
    if (Variables[SIGMA - 1] <= Solution) {
        Solution -= Variables[SIGMA - 1];
        SolutionSign = 1;
    } else {
        Solution = Variables[SIGMA - 1] - Solution;
        SolutionSign = -1;
    }
}

void Read() {
    assert(freopen("eval.in", "r", stdin));
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string number, digits;
        cin >> number;
        if (number[0] == '-') {
            for (int i = 1; i < static_cast<int>(number.size()); ++i)
                digits.push_back(number[i]);
            Signs[i] = -1;
        } else {
            digits = number;
            Signs[i] = 1;
        }
        Variables[i] = BigInt(digits);
    }
    string maxValue = "1";
    for (int i = 1; i <= 1000; ++i)
        maxValue += "0";
    string expression;
    cin >> expression;
    expression += "+";
    expression.push_back(static_cast<char>('a' + SIGMA - 1));
    Variables[SIGMA - 1] = BigInt(maxValue);
    for (int i = 0; i < static_cast<int>(expression.length()); ++i)
        Expression[i] = expression[i];
    Expression[static_cast<int>(expression.length())] = '\0';
}

void Print() {
    assert(freopen("eval.out", "w", stdout));
    if (SolutionSign == -1)
        printf("-");
    Solution.Print(stdout);
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}