Cod sursa(job #131075)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 3 februarie 2008 09:07:32
Problema Eval Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.47 kb
#include <stdio.h>
#include <string.h>

#define MAXVL 200
#define BAZA 1000000
#define OUTPUT_FORMAT "%06d"
#define MAXL 100005
#define NRPR 108

int N;
int val[32][MAXVL], valMod[32]; char valNeg[32];

char tmp[1024];

char expr[MAXL], *p; int MOD;
const int PRIM[NRPR] = {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};

int prod[MAXVL], rest[MAXVL];

//Numere mari
inline void add( int A[], int B[] )
{
	int i, t = 0;
	for (i = 1; i <= A[0] || i <= B[0] || t; i++, t /= BAZA)
		A[i] = (t += A[i] + B[i]) % BAZA;
	A[0] = i - 1;
}

inline void sub( int A[], int B[] )
{
	int i, t = 0;

	for (i = 1; i <= A[0]; i++)
	{
		A[i] -= B[i] + t;
		A[i] += (t = A[i] < 0) * BAZA;
	}

	for (; A[0] && !A[A[0]]; A[0]--);
}

inline void mul( int A[], int B )
{
	if (B == 0)
	{
		memset(A, 0, sizeof(int) * MAXVL);
		A[0] = 1;
		return;
	}

	int C[MAXVL], i; long long t = 0;
	memset( C, 0, sizeof(C) );
	for (i = 1; i <= A[0] || t; i++, t /= BAZA)
		C[i] = (t += (long long)A[i] * B) % BAZA;
	C[0] = i - 1;
	memcpy( A, C, sizeof(C) );
}
 
inline int mod( int A[], int B )
{
	int i; long long t = 0;
	for (i = A[0]; i >= 1; i--)
		t = (t * BAZA + A[i]) % B;
	return t;
}

inline void print( int A[] )
{
	printf("%d", A[ A[0] ]);
	for (int i = A[0] - 1; i >= 1; i--)
		printf("%06d", A[i]);
	printf("\n");
}

inline int cmp( int A[], int B[] )
{
	if (A[0] < B[0])
		return -1;
	if (A[0] > B[0])
		return 0;

	for (int i = A[0]; i >= 0; i--)
		if (A[i] != B[i])
			if (A[i] < B[i])
				return -1;
			else
				return 1;
	return 0;
}

//Evaluare expresii
int expresie();
int factor()
{
	if (*p == '+')		//operator unar
	{
		p++;
		return factor();
	}
	if (*p == '-')		//operator unar
	{
		p++;
		return MOD - factor();
	}
	if (*p == '(' || *p == '[')
	{
		int type = (*p == '[');
		p++;
		int rez = expresie();
		p++;

		if (type)
			return ((long long)rez * rez) % MOD;
		return rez;
	}

	int rez = valMod[ *p - 'a' ]; p++;
	return rez;
}

int termen()
{
	int rez = factor();
	for (; *p == '*'; )
	{
		p++;
		rez = ((long long)rez * factor()) % MOD;
	}
	return rez;
}

int expresie()
{
	int rez = termen();
	for (; *p == '+' || *p =='-'; )
		if (*p == '+')
		{
			p++;
			rez = ((long long)rez + termen()) % MOD;
		}
		else
		{
			p++;
			rez = ((long long)rez - termen() + MOD) % MOD;
		}
	return rez;
}

//GCD extins
int gcd( int A, int B, int &X, int &Y )
{
	if (B == 0)
	{
		X = 1;
		Y = 0;
		return A;
	}

	int X0, Y0;
	int D = gcd( B, A % B, X0, Y0 );
	//D == B * X0 + (A % B) * Y0
	//D == B * X0 + (A - [A / B] * B) * Y0
	//D == B * X0 + A * Y0 - B * [A / B] * Y0
	
	X = Y0;
	Y = X0 - (A / B) * Y0;
	return D;
}

int main()
{
	freopen("eval.in", "rt", stdin);
	freopen("eval.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf(" %s", tmp);
		int poz;
		for (poz = (tmp[0] == '-'); '0' <= tmp[poz] && tmp[poz] <= '9'; poz++);

		int put = 1, cif = 0;
		for (poz--; '0' <= tmp[poz] && tmp[poz] <= '9'; poz--)
		{
			cif += put * (tmp[poz] - '0');
			put *= 10;
			if (put == BAZA)
				val[i][ ++val[i][0] ] = cif,
				cif = 0, put = 1;
		}
		if (cif)
			val[i][ ++val[i][0] ] = cif;
		if (tmp[0] == '-')
			valNeg[i] = 1;
	}

	//adun 10^1000 la rezultat ca sa nu dea negativ
	val[N][ val[N][0] = 1 ] = 1;
	for (int k = 1; k <= 1000; k++)
		mul( val[N], 10 );

	scanf(" %s", tmp);
	sprintf( expr, "(%s)+%c", tmp, 'a' + N );

	memset( prod, 0, sizeof(prod) ); prod[ prod[0] = 1 ] = 1;
	memset( rest, 0, sizeof(rest) ); rest[0] = 1;
	for (int i = 0; i < NRPR; i++)
	{
		p = expr; MOD = PRIM[i];
		for (int j = 0; j <= N; j++)
		{
			valMod[j] = mod( val[j], MOD );
			if (valNeg[j])
				valMod[j] = MOD - valMod[j];
		}
		int curRest = expresie();

		//Pentru 2 numere (X1, X2) prime intre ele tb sa rezolv sistemul
		//N === R1 (mod X1)
		//N === R2 (mod X2)
	
		//X1 * C1 + R1 == X2 * C2 + R2
		//X1 * C1 - X2 * C2 == R2 - R1
		
		int D, X0, Y0;
		D = gcd( PRIM[i], mod( prod, PRIM[i] ), X0, Y0 );
		//X = Y0;
		//Y = (prod / PRIM[i]) * Y0 - X0;
	
		int tmp[MAXVL];
		memcpy( tmp, prod, sizeof(tmp) );

		mul( tmp, (MOD + ((long long)Y0 * ((long long)curRest - mod( rest, MOD )) % MOD)) % MOD );
		add( tmp, rest );

		mul( prod, PRIM[i] );
		memcpy( rest, tmp, sizeof(rest) );
	}
	
	if ( cmp( rest, val[N] ) < 0 )
	{
		printf("-");
		sub( val[N], rest );
		print(val[N]);
	}
	else
	{
		sub( rest, val[N] );
		print(rest);
	}

	return 0;
}