Cod sursa(job #74656)

Utilizator wefgefAndrei Grigorean wefgef Data 26 iulie 2007 21:01:42
Problema Sarpe Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>

#define base 10
#define Nmax 1000005

typedef int huge[Nmax];

char s[Nmax];
int A[Nmax], B[Nmax];

void readdata()
{
	freopen("sarpe.in", "r", stdin);
	freopen("sarpe.out", "w", stdout);

	int i;

	fgets(s, Nmax, stdin);
	for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
		A[i+1] = s[i]-'0';
	A[0] = i;
}

inline void sch(int &a, int &b) { a^= b ^= a^= b; }

void multiply()
{
	int i, j, t = 0;

	for (i = 1; i <= A[0]; ++i)
		for (j = 1; j <= A[0]; ++j)
			B[i+j-1] += A[i]*A[j];

	for (i = 1; i <= 2*A[0]-1 || t; ++i, t /= base)
		B[i] = (t += B[i]) % base;
	B[0] = i-1;
}

void scade()
{
	int i;

	for (i = 1; i <= B[0]; ++i)
	{
		if (B[i] < A[i])
		{ B[i] += 10; --B[i+1]; }
		B[i] -= A[i];
	}
	while (B[0] && B[B[0]] == 0) --B[0];
}

void aduna()
{
	int i, t = 0;

	for (i = 1; i <= B[0] || t; ++i, t /= base)
	{
		if (i == 1) B[i] += 2;
		B[i] = (t += B[i]) % base;
	}
	B[0] = i-1;
}

void inmulteste()
{
	int i, t = 0;

	for (i = 1; i <= B[0] || t; ++i, t /= base)
		B[i] = (t += B[i]*2) % base;
	B[0] = i-1;
}

void solve()
{
	int i, j;

	//caz particular
	if (A[0] == A[1] && A[0] == 1)
	{
		printf("1\n");
		return;
	}

	for (i = 1, j = A[0]; i < j; ++i, --j)
		sch(A[i], A[j]);

	multiply();
	scade();
	aduna();
	inmulteste();
	for (i = B[0]; i; --i)
		printf("%d", B[i]);
}

int main()
{
	readdata();
	solve();
	return 0;
}