Cod sursa(job #419297)

Utilizator FlorianFlorian Marcu Florian Data 17 martie 2010 11:49:10
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
using namespace std;
#include<fstream>
const int MAX_N = 10007;
int p[10][10][10];
int S[MAX_N], N, Sum;
int main()
{
	ifstream in("koba.in"); ofstream out("koba.out");
	int a, b, c, i, lg, d, j, s, tmp;
	in>>N>>a>>b>>c;
	if(N == 1) { out<<a%10<<"\n"; return 0; }
	if(N == 2) { out<<(a%10+b%10)<<"\n"; return 0; }
	if(N == 3) { out<<(a%10+b%10+c%10)<<"\n"; return 0; }
	a%=10, b%=10, c%=10;
	S[1] = a, S[2] = a+b, S[3] = a+b+c; p[a][b][c] = 1;
	for(i = 4; i <= N; ++i)
	{
		d = (c + (a * b)) % 10;
		a = b;
		b = c;
		c = d;
		S[i] = S[i-1] + d;
		if(!p[a][b][c]) p[a][b][c] = i-2;
		else
		{
			j = p[a][b][c];
			Sum = S[j-1];
			s = S[i-3] - S[j-1];
			lg = i - j - 2;
			N = N - j + 1;
			tmp = (N/lg) * s;
			Sum += tmp;
			tmp = S[j + (N%lg)-1] - S[j-1];
			Sum += tmp;
			break;
		}
	}
	if(i == N + 1) Sum = S[N];
	out<<Sum<<"\n";
	return 0;
}