Cod sursa(job #754157)

Utilizator GrimpowRadu Andrei Grimpow Data 31 mai 2012 21:20:05
Problema Sarpe Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <cstdio>
#include <string>

#define dim 2048

using namespace std;

int N[dim];
int A[dim];
int B[dim];
int C[dim];

string S;

int SOL;

void Subtract(int *X, int v)
{
	int i, t = 0;
	
	memcpy(X, N, sizeof(N));
	
	X[1] -= v;
	for(i=1; i<=X[0]; ++i)
	{
		X[i] -= t;
		if(X[i] < 0)
		{
			X[i] += 10;
			t = 1;
		}
		else t = 0;
	}
	
	while(!X[X[0]] && X[0] > 1) -- X[0];
}

void Mults(int *A, int v)
{
	int i, t = 0;
	
	for(i=1; i<=A[0]; ++i)
	{
		A[i] *= v;
		A[i] += t;
		t = A[i] / 10;
		A[i] %= 10;
	}
	
	while(t)
	{
		A[++A[0]] = t % 10;
		t /= 10;
	}
}

void Multiply(int *A, int *B)
{
	C[0] = A[0] + B[0] - 1;
	
	int i, j, t = 0;
	for(i=1; i<=A[0]; ++i)
		for(j=1; j<=B[0]; ++j)
			C[i+j-1] += A[i] * B[j];
			
	for(i=1; i<=C[0]; ++i)
	{
		C[i] += t;
		t = C[i] / 10;
		C[i] %= 10;
	}
	
	if(t) C[++C[0]] = t;
}

void Add(int *A, int *B)
{
	A[0] = A[0] > B[0] ? A[0] : B[0];
	
	int i, t = 0;
	for(i=1; i<=A[0]; ++i)
	{
		A[i] += B[i] + t;
		t = A[i] / 10;
		A[i] %= 10;
	}
	
	if(t) A[++A[0]] = t;
}

int main()
{
	freopen("sarpe.in", "rt", stdin);
	freopen("sarpe.out", "wt", stdout);
	
	cin >> S;

	if(S.length() == 1 && S[0] == '1') SOL = 1;

	int i, n, c;
	for(n=S.length(), i=n-1; i>=0; --i)
	{
		c = (int) S[i] - '0';
		N[++N[0]] = c;
	}
	
	Subtract(A, 1);
	Subtract(B, 2);
	
	Mults(N, 4);
	Mults(A, 2);
	Multiply(A, B);
	Add(N, C);

	if(SOL) printf("2");
	else
		for(i=N[0]; i; --i)
			printf("%d", N[i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}