Cod sursa(job #791675)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 septembrie 2012 20:19:28
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.14 kb
#include <cstdio>
#include <cstring>

const int Vmax = 200;
const int Baza = 1000000;
const int Lmax = 100005;
const int NPr = 108;

typedef long long (I64);

#define out_f "%06d"

int N;
int V[32][Vmax], A[32]; char B[32];

char Buff[Lmax];

char Expr[Lmax], *p; int Mod;
const int Prim[NPr] = {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 P[Vmax], R[Vmax];


void Sum( 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;
}

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

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

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

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

	int C[Vmax], i; I64 t = 0;
	memset( C, 0, sizeof(C) );
	for (i = 1; i <= A[0] || t; ++i, t /= Baza)
		C[i] = (t += (I64) A[i] * B) % Baza;
	C[0] = i - 1;
	memcpy( A, C, sizeof(C) );
}
 
int Modulo( int A[], int B )
{
	int i; I64 t = 0;
	for (i = A[0]; i >= 1; i--)
		t = (t * Baza + A[i]) % B;
	return t;
}

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

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

	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;
}

int Eval();
int Fact();
int Term();

int Euclid( int A, int B, int &X, int &Y )
{
	if (B == 0)
	{
		X = 1;
		Y = 0;
		return A;
	}

	int X0, Y0;
	int D = Euclid( B, A % B, X0, 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", Buff);
		int poz;
		for (poz = (Buff[0] == '-'); '0' <= Buff[poz] && Buff[poz] <= '9'; poz++);

		int put = 1, cif = 0;
		for (poz--; '0' <= Buff[poz] && Buff[poz] <= '9'; poz--)
		{
			cif += put * (Buff[poz] - '0');
			put *= 10;
			if (put == Baza)
				V[i][ ++V[i][0] ] = cif,
				cif = 0, put = 1;
		}
		if (cif)
			V[i][ ++V[i][0] ] = cif;
		if (Buff[0] == '-')
			B[i] = 1;
	}

	V[N][ V[N][0] = 1 ] = 1;
	for (int k = 1; k <= 1000; k++)
		Mul( V[N], 10 );

	scanf(" %s", Buff);
	sprintf( Expr, "(%s)+%c", Buff, 'a' + N );

	memset( P, 0, sizeof(P) ); P[ P[0] = 1 ] = 1;
	memset( R, 0, sizeof( R ) ); R[0] = 1;
	for (int i = 0; i < NPr; ++i)
	{
		p = Expr; Mod = Prim[i];
		for (int j = 0; j <= N; ++j)
		{
			A[j] = Modulo( V[j], Mod );
			if (B[j])
				A[j] = Mod - A[j];
		}
		int Act = Eval();
		
		int D, X0, Y0;
		D = Euclid( Prim[i], Modulo( P, Prim[i] ), X0, Y0 );
		
		int Buff[Vmax];
		memcpy( Buff, P, sizeof(Buff) );
		
		Mul( Buff, (Mod + ((I64) Y0 * ((I64) Act - Modulo( R, Mod )) % Mod)) % Mod );
		Sum( Buff, R );
		
		Mul( P, Prim[i] );
		memcpy( R, Buff, sizeof( R ) );
	}
	if ( Comp( R, V[N] ) < 0 )
	{
		printf("-");
		Sub( V[N], R );
		print(V[N]);
	}
	else
	{
		Sub( R, V[N] );
		print( R );
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}


int Fact()
{
	if (*p == '+')		
	{
		++p;
		return Fact();
	}
	if (*p == '-')		
	{
		++p;
		return Mod - Fact();
	}
	if (*p == '(' || *p == '[')
	{
		int type = (*p == '[');
		++p;
		int rez = Eval();
		++p;

		if (type)
			return ((I64) rez * rez) % Mod;
		return rez;
	}

	++p;
	return A[ *(p-1) - 'a' ];
}

int Term()
{
	int rez = Fact();
	for (; *p == '*'; )
	{
		++p;
		rez = ((I64) rez * Fact()) % Mod;
	}
	return rez;
}

int Eval()
{
	int rez = Term();
	for (; *p == '+' || *p =='-'; )
		if (*p == '+')
		{
			++p;
			rez = ((I64) rez + Term()) % Mod;
		}
		else
		{
			++p;
			rez = ((I64) rez - Term() + Mod) % Mod;
		}
	return rez;
}