Cod sursa(job #467394)

Utilizator funkydvdIancu David Traian funkydvd Data 28 iunie 2010 17:23:17
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
using namespace std;
int p[10][10][10],S[10007], N, suma;
ifstream f1("koba.in"); 
ofstream f2("koba.out");
int main()
{
	int a, b, c, i, nr, d, j, s, s2;
	f1>>N>>a>>b>>c;
	if(N == 1) { f2<<a%10<<"\n"; return 0;}
	if(N == 2) { f2<<(a%10+b%10)<<"\n"; return 0;}
	if(N == 3) { f2<<(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  // am gasit aceiasi 3 termeni, deci suma poate fi calculata matematic
		{
			j = p[a][b][c]; //pozitia la care am avut cei 3 termeni ultima oara
			suma = S[j-1];  //suma pana la acea pozitie
			s = S[i-3] - S[j-1]; //suma care se repeta periodic
			nr = i - j - 2; // nr de termeni pe care ii contine un ciclu
			N = N - j + 1; // termenii care au ramas
			s2 = (N/nr) * s; // suma urmatoarelor cicluri, pana in N
			suma += s2;
			s2 = S[j + (N%nr)-1] - S[j-1]; //suma termenilor aflati in afara ciclului
			suma+= s2;
			break;
		}
	}
	if(i == N + 1) suma=S[N];
	f2<<suma<<"\n";
	return 0;
}