Cod sursa(job #148360)

Utilizator webspiderDumitru Bogdan webspider Data 4 martie 2008 10:46:37
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <stdio.h>
#include <iostream>

using namespace std;

const int bz = 1000;
const int maxN = 1001;

typedef int ll[ maxN ];

ll N, A1, A2, A3, SOL;
char aux[ maxN ];

void multC( ll A, int C, ll &dest ) {
	int r = 0;
	ll aux; memset( aux, 0, sizeof( aux ) );
	for ( int i = 1; i <= A[0] || r ; i++ ) {
		aux[ i ] = A[ i ] * C + r;
		r = aux[ i ] / bz;
		aux[ i ] = aux[ i ] % bz;
		if ( i > aux[ 0 ] ) aux[ 0 ] = i;
	}
	memcpy( dest, aux, sizeof( aux ) );
}

void addC( ll A, int C, ll &dest ) {
	ll aux; memset( aux, 0, sizeof( aux ) );
	aux[ 0 ] = A[0];
	aux[ 1 ] += C;
	for ( int i = 1; i <= aux[0]; i++ ) {
		aux[ i ] += A[i];
		if ( aux[i] < 0 ) {
			aux[i] += bz;
			aux[i+1] -= 1;
		}
	}
	while ( !aux[ aux[0] ] ) aux[0]--;
	memcpy( dest, aux, sizeof( aux ) );
}

void addN( ll A, ll B, ll &dest ) {
	int r = 0;
	ll aux; memset( aux, 0, sizeof( aux )  );
	aux[ 0 ] = max( A[0], B[0] );
	for ( int i = 1; i <= aux[0] || r; i++ ) {
		aux[ i ] = A[i]+B[i]+r;
		r = aux[i] / bz;
		aux[i] = aux[i]%bz;
		if ( i > aux[0] ) aux[0] = i;
	}
	memcpy( dest, aux, sizeof( aux ) );
}

int multN( ll A, ll B, ll &dest ) {
	ll aux; memset( aux, 0, sizeof( aux ) );
	int r = 0;

	for ( int i = 1; i <= A[0]; i++ ) {
		for ( int j = 1; j <= B[0]; j++ ) {
			aux[ j + i - 1 ] += A[i] * B[j];
			aux[ 0 ] = max( aux[0], j + i - 1 );
		}
		for ( int j = 1; j <= aux[0] || r; j++ ) {
			aux[j] += r;
			r = aux[j] / bz;
			aux[ j ] = aux[j] % bz;
			aux[0]= max( aux[0],j );
		}
	}
	memcpy( dest, aux, sizeof( aux ) );
}

void printN( ll A ) {
	printf("%d", A[ A[0] ] );
	for ( int i = A[0]-1; i >= 1; i-- ) 
		printf("%.3d", A[i] );
}



int main()
{
	int X= 1;
	freopen("sarpe.in","r",stdin);
	freopen("sarpe.out","w",stdout);

	scanf("%s\n", aux );
	N[ 0 ] = 1;
	for ( int i = strlen( aux ) - 1; i >= 0; i-- ) {
		N[ N[0] ] += X*(aux[ i ] - '0');
		X *= 10;
		if ( X == bz ) {
			X = 1;
			N[0]++;
		}
	}
	if ( N[0] == N[1] == 1 ) {
		printf("2\n");
		return 0;
	}

	multC( N, 4, A1 );
	addC( N, -1, A2 );
	addC( N, -2, A3 );
	multN( A2, A3, SOL );
	multC( SOL, 2, SOL );
	addN( SOL, A1, SOL );
	printN( SOL );

	return 0;
}