Cod sursa(job #139081)

Utilizator damaDamaschin Mihai dama Data 19 februarie 2008 18:16:39
Problema Sarpe Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <string.h>
#include <ctype.h>


const int baza = 10000;

char line[1024];
int n[2048], sol[2048];


void mul(int*, int*, int*);
void mul(int*, int);

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

	int i, len;

	fgets(line, 1024, stdin);

	len = strlen(line - 1);
	for(i = len; i >= 0; --i)
	{
		if(isdigit(line[i]))
		{
			n[++n[0]] = line[i] - '0';
		}
	}
	if(n[0] == n[1] && n[0] == 1)
	{
		printf("2\n");
		return 0;
	}

	memcpy(sol, n, sizeof(sol));
	--n[1];
	i = 1;
	while(n[i] == -1)
	{
		n[i] += 10;
		--n[i + 1];
		++i;
	}
	if(!n[n[0]])
		--n[0];
	mul(sol, sol, n);
	sol[1] += 2;
	i = 1;
	while(sol[i] >= 10)
	{
		sol[i] -= 10;
		++sol[i + 1];
		++i;
	}
	if(sol[sol[0] + 1])
		sol[0];
	mul(sol, 2);

	printf("%d",  sol[sol[0]]);
	for(i = sol[0] - 1; i > 0; --i)
	{
		printf("%04d", sol[i]);
	}
	printf("\n");

	return 0;
}

void mul(int* a, int b)
{
	int i, t;
	for(i = 1, t = 0; i <= a[0] || t; ++i, t /= baza)
	{
		a[i] = (t += a[i] * b) % baza;
	}
	a[0] = i - 1;
}

void mul(int* dest, int* a, int* b)
{
	int c[2048], i, j, t;
	memset(c, 0, sizeof(c));
	for(i = 1; i <= a[0]; ++i)
	{
		for(j = 1, t = 0; j <= b[0] || t; ++j, t /= baza)
		{
			c[i + j - 1] = (t += c[i + j - 1] + a[i] * b[j]) % baza;
		}
		if(i + j - 2 > c[0])
		{
			c[0] = i + j - 2;
		}
	}
	memcpy(dest, c, sizeof(c));
}