Cod sursa(job #461415)

Utilizator SpiderManSimoiu Robert SpiderMan Data 6 iunie 2010 18:37:31
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>

const char FIN[] = "koba.in", FOU[] = "koba.out";
const int MAX = 10005;

int verf[10][10][10];
int S[MAX] ;
int N, A, B, C;

void solve ()
{
    int sol = 0;

    S[1] = A, S[2] = A + B, S[3] = A + B + C, verf[A][B][C] = 1;

	for (int i = 4; i <= N; ++i)
	{
		int D = ( C + ( A * B ) ) % 10;

		A = B, B = C, C = D;
		S[i] = S[i - 1] + D;

		if ( verf[A][B][C] == 0 ) verf[A][B][C] = i - 2;
		else
		{
			int j = verf[A][B][C], solt = S[i - 3] - S[j - 1], dif = i - j - 2;

            sol = S[j - 1];

			N -= j, ++N;

			int aux = ( N / dif ) * solt;

			sol += aux;

			sol += ( aux = S[ j + ( N % dif ) - 1 ] - S[ j - 1 ] );

			break;
		}

		if ( i == N ) sol = S[N];
	}

	printf("%d", sol);
}
int main()
{
    freopen ( FIN , "r" , stdin );
    freopen ( FOU , "w" , stdout );

	scanf ("%d %d %d %d", &N, &A, &B, &C);

	A %= 10, B %= 10, C %= 10;

	if (N == 1)  printf("%d", A);
	else if (N == 2)  printf("%d", A + B);
	else if (N == 3)  printf("%d", A + B + C);
	else solve ();

	return 0;
}