Cod sursa(job #1873357)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 8 februarie 2017 23:13:01
Problema Eval Scor 90
Compilator cpp Status done
Runda Lista lui wefgef Marime 7.95 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>

const int kPrimeCount = 108;
const int kPrimes[] = {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};
const int kMaxDim = 100005;
const int kMaxSigma = 30;

#define A (*this)
class Huge : protected std::vector < int > {
	protected:
		static const int base = 1000000000, nBase = 9, maxCif = 1000/9 + 20;

	public:

		Huge() {
			this->resize(maxCif);
		}

		Huge(int x) {
			this->resize(maxCif);
			A = x;
		}

		Huge(const char* s) {
			this->resize(maxCif);
			A = s;
		}

		Huge& operator = (int x) {
			for (A[0] = 0; x; x /= base)
				A[++A[0]] = x % base;
			return A;
		}

		Huge& operator = (const char *s) {
			A[0] = 0;
			for (int i = strlen(s); i > 0; i -= nBase) {
				++A[0];
				A[A[0]] = 0;
				for (int j = std::max(0, i - nBase); j < i; ++j)
					A[A[0]] = A[A[0]] * 10 + s[j] - '0';
			}
			return A;
		}

		friend std::ostream& operator << (std::ostream& outStream, const Huge& B) {
			if (B[0] == 0) {
				outStream << 0;
				return outStream;
			}
			outStream << B[B[0]];
			for (int i = B[0] - 1; i > 0; --i) {
				int p = base / 10;
				while (p > B[i] && p > 1) {
					outStream << 0;
					p /= 10;
				}
				outStream << B[i];
			}
			return outStream;
		}

		bool operator < (const Huge &B) const {
			if (A[0] != B[0])
				return A[0] < B[0];
			for (int i = A[0]; i; --i) {
				if (A[i] < B[i]) return true;
				if (B[i] < A[i]) return false;
			}
			return false;
		}

		Huge operator + (const Huge &B) {
			int i, t = 0;
			Huge C;
			for (i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= base) {
				t += (i <= A[0] ? A[i] : 0);
				t += (i <= B[0] ? B[i] : 0);
				C[i] = t % base;
			}
			C[0] = i - 1;
			return C;
		}

		Huge operator - (const Huge &B) {
			Huge C = A;
			int i, t = 0;
			for (i = 1; i <= A[0]; ++i) {
				C[i] -= (i <= B[0] ? B[i] : 0) + t;
				t = 0;
				if (C[i] < 0) C[i] += base, t = 1;
			}
			while (C[0] > 1 && C[C[0]] == 0)
				--C[0];
			return C;
		}

		Huge operator * (int x) {
			Huge C = A;
			long long t = 0;
			for (int i = 1; i <= C[0]; ++i) {
				t = 1LL * C[i] * x + t;
				C[i] = t % base;
				t /= base;
			}
			while (t) {
				C[++C[0]] = t % base;
				t /= base;
			}
			return C;
		}

		Huge operator * (const Huge &B) {
			Huge C;
			for (int i = 1; i <= A[0]; ++i) {
				long long t = 0; int j;
				for (j = 1; j <= B[0] || t; ++j, t /= base) {
					t += C[i + j - 1] + (j <= B[0] ? 1LL * A[i] * B[j] : 0);
					C[i + j - 1] = t % base;
				}
				if (i + j - 2 > C[0])
					C[0] = i + j - 2;
			}
			return C;
		}

		Huge operator / (int x) {
			Huge C;
			C = A;
			long long R = 0;
			for (int i = A[0]; i; --i) {
				R = R * base + A[i];
				C[i] = int(R / x);
				R %= x;
			}
			while (C[0] > 1 && C[C[0]] == 0)
				--C[0];
			return C;
		}

		int operator % (int x) {
			long long R = 0;
			for (int i = A[0]; i; --i) {
				R = R * base + A[i];
				R %= x;
			}
			return (int)R;
		}

		bool operator == (Huge B) {
			if (A.isZero() && B.isZero())
				return true;
			if (A[0] != B[0])
				return false;
			for (int i = 1; i <= A[0]; ++i)
				if (A[i] != B[i])
					return false;
			return true;
		}

		int getInt(void) {
			int ret = 0;
			for (int i = 1; i <= A[0]; ++i)
				ret = ret * 10 + A[i];
			return ret;
		}

		bool isZero(void) {
			int ok = true;
			for (int i = A[0]; i && ok; --i)
				if (A[i] != 0)
					ok = false;
			if (ok)
				A[0] = 0;
			return ok;
		}

		Huge& operator += (const Huge& B) {
			A = A + B;
			return A;
		}

		Huge& operator *= (int x) {
			A = A * x;
			return A;
		}

		Huge& operator *= (const Huge& B) {
			A = A * B;
			return A;
		}

		Huge& operator -= (const Huge& B) {
			A = A - B;
			return A;
		}

		Huge& operator /= (int x) {
			A = A / x;
			return A;
		}
};
#undef A

Huge values[kMaxSigma];
int remainders[kPrimeCount];

char expression[kMaxDim];
int indx, modulo;
int valuesModulo[kMaxSigma];
int ComputeExpression();
int ComputeTerm();
int ComputeFactor();

int ComputeExpression() {
	int res = ComputeTerm();
	while (expression[indx] == '+' || expression[indx] == '-') {
		if (expression[indx] == '+') {
			indx++;
			res = (1LL * res + ComputeTerm()) % modulo;
		}
		else {
			indx++;
			res = (1LL * res - ComputeTerm() + modulo) % modulo;
		}
	}
	return res;
}

int ComputeTerm() {
	int res = ComputeFactor();
	while (expression[indx] == '*') {
		indx++;
		res = (1LL * res * ComputeFactor()) % modulo;
	}
	return res;
}

int ComputeFactor() {
	int res = 0;
	if (expression[indx] == '(') {
		indx++;
		res = ComputeExpression();
		indx++;
	}
	else if (expression[indx] == '[') {
		indx++;
		res = ComputeExpression();
		res = (1LL * res * res) % modulo;
		indx++;
	}
	else if (expression[indx] == '+') {
		indx++;
		res = ComputeExpression();
	}
	else if (expression[indx] == '-') {
		indx++;
		res = -ComputeExpression();
		res = (1LL * res + modulo) % modulo;
	}
	else {
		res = valuesModulo[expression[indx] - 'a'];
		indx++;
	}
	return res;
}

int RaiseToPower(int who, int power, int modulo) {
	int res = 1;
	while (power > 0) {
		if (power & 1)
			res = (1LL * res * who) % modulo;
		who = (1LL * who * who) % modulo;
		power >>= 1;
	}
	return res;
}

char s[kMaxDim];

int main() {
	std::ifstream inputFile("eval.in");
	std::ofstream outputFile("eval.out");

	int valueCount;
	inputFile >> valueCount;

	for (int i = 0; i < valueCount; ++i) {
		inputFile >> s;
		values[i] = s;
	}

	inputFile >> expression;

	for (int i = 0; i < kPrimeCount; ++i) {
		modulo = kPrimes[i];
		indx = 0;
		for (int j = 0; j < valueCount; ++j)
			valuesModulo[j] = values[j] % modulo;

		int res = ComputeExpression();
		res = (1LL * res + RaiseToPower(10, 1000, modulo)) % modulo;
		remainders[i] = res;
	}

	Huge prime1 = kPrimes[0], remainder1 = remainders[0];
	for (int i = 1; i < kPrimeCount; ++i) {
		Huge prime2 = kPrimes[i], remainder2 = remainders[i];

		//x = p1*((p1'*l) % p2) + r1 (mod p1*p2)
		int l = (1LL * (remainder2 % kPrimes[i]) - (remainder1 % kPrimes[i]) + kPrimes[i]) % kPrimes[i];
		int p1Inv = RaiseToPower((prime1 % kPrimes[i]), kPrimes[i] - 2, kPrimes[i]);

		Huge temp = (1LL * l * p1Inv) % kPrimes[i];
		temp *= prime1;

		remainder1 += temp;
		prime1 *= prime2;
	}

	std::string aux = "1";
	for (int i = 1; i <= 1000; ++i)
		aux += "0";

	Huge temp(aux.data());
	remainder1.isZero();
	if (remainder1 < temp)
		outputFile << "-" << temp - remainder1 << '\n';
	else
		outputFile << remainder1 - temp << '\n';

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!