Cod sursa(job #203260)

Utilizator vmaneavmanea vmanea Data 14 august 2008 22:17:30
Problema Koba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>

int este[16][16][16], pre, crt;

int suma, suma1, suma2, suma3, suma4;

int main()
{
	int N, T1, T2, T3, T4, T5, T6, aux, i;

	freopen("koba.in", "r", stdin);
	freopen("koba.out", "w", stdout);

	scanf("%d%d%d%d", &N, &T1, &T2, &T3);

	T1 %= 10, T2 %= 10, T3 %= 10, T4 = T1, T5 = T2, T6 = T3, este[T1][T2][T3] = 3, suma = T1+T2+T3;

	for (i = 4; i <= N && !crt; ++i)
	{
		aux = (T3 + T2 * T1) % 10;
		T1 = T2, T2 = T3, T3 = aux;
		suma += aux;

		if (!este[T1][T2][T3])
			este[T1][T2][T3] = i;
		else
		{
			pre = este[T1][T2][T3];
			crt = i;
		}
	}

	if (pre == 0)
		printf("%d\n", suma);
	else
	{
		// calculez suma de la T1 pana la pre
		for (T1 = T4, T2 = T5, T3 = T6, suma1 = T1+T2+T3, i = 4; i <= pre; ++i)
		{
			aux = (T3 + T2 * T1) % 10;
			T1 = T2, T2 = T3, T3 = aux;
			suma1 += aux;
		}

		// calculez suma de la pre+1 pana la crt
		for (i = pre+1; i <= crt; ++i)
		{
			aux = (T3 + T2 * T1) % 10;
			T1 = T2, T2 = T3, T3 = aux;
			suma2 += aux;
		}

		// vad cate mai raman
		suma3 = (N-pre)/(crt-pre);

		suma3 *= suma2;

		// calculez cate mai raman
		for (T1 = T4, T2 = T5, T3 = T6, i = pre+(N-pre)/(crt-pre)*(crt-pre)+1; i <= N; ++i)
		{
			aux = (T3 + T2 * T1) % 10;
			T1 = T2, T2 = T3, T3 = aux;
			suma4 += aux;
		}

		printf("%d\n", suma1+suma3+suma4);
	}

	return 0;
}