Cod sursa(job #1873363)

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

const int kPrimeCount = 120;
const int kPrimes[] = {1999997017, 1999997089, 1999997107, 1999997117, 1999997141, 1999997159, 1999997189, 1999997203, 1999997213, 1999997239, 1999997273, 1999997341, 1999997359, 1999997393, 1999997411, 1999997413, 1999997429, 1999997459, 1999997491, 1999997537, 1999997543, 1999997563, 1999997569, 1999997579, 1999997599, 1999997603, 1999997611, 1999997621, 1999997633, 1999997641, 1999997663, 1999997689, 1999997711, 1999997719, 1999997773, 1999997777, 1999997807, 1999997849, 1999997873, 1999997887, 1999997903, 1999997941, 1999997957, 1999997971, 1999997981, 1999998029, 1999998047, 1999998103, 1999998149, 1999998181, 1999998193, 1999998239, 1999998313, 1999998347, 1999998359, 1999998383, 1999998389, 1999998401, 1999998421, 1999998443, 1999998457, 1999998479, 1999998493, 1999998527, 1999998551, 1999998617, 1999998631, 1999998641, 1999998701, 1999998719, 1999998733, 1999998743, 1999998761, 1999998769, 1999998773, 1999998797, 1999998799, 1999998809, 1999998823, 1999998827, 1999998857, 1999998893, 1999998899, 1999998907, 1999998941, 1999998947, 1999998961, 1999999003, 1999999013, 1999999049, 1999999061, 1999999081, 1999999087, 1999999093, 1999999097, 1999999117, 1999999121, 1999999151, 1999999171, 1999999207, 1999999219, 1999999271, 1999999321, 1999999373, 1999999423, 1999999439, 1999999499, 1999999553, 1999999559, 1999999571, 1999999609, 1999999613, 1999999621, 1999999643, 1999999649, 1999999657, 1999999747, 1999999763, 1999999777, 1999999811};
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];
		if (!temp.isZero()) {
			temp *= prime1;
			remainder1 += temp;
		}

		prime1 *= prime2;
	}

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

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

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

	return 0;
}

//Trust me, I'm the Doctor!