Cod sursa(job #595204)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 11 iunie 2011 14:57:45
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
# include <fstream>
using namespace std;

int t1, t2, t3, t4, ap[1000][2];
int i, n, sol, val;
int main ()
{
	ifstream f ("koba.in");
	ofstream g ("koba.out");
	
	f >> n >> t1 >> t2 >> t3;
	t1 = t1 % 10;
	t2 = t2 % 10;
	t3 = t3 % 10;
	sol = t1 + t2 + t3;
	ap[t1 * 100 + t2 * 10 + t3][0] = sol;
	ap[t1 * 100 + t2 * 10 + t3][1] = 3;
	
	for (i = 4; i <= n; ++i)
	{
		t4 = (t3 + t2 * t1) % 10;
		sol += t4;
		
		t1 = t2;
		t2 = t3;
		t3 = t4;
		
		val = t1 * 100 + t2 * 10 + t3;
		
		if (!ap[val][0])
		{
			ap[val][0] = sol;
			ap[val][1] = i;
		}
		else
		{
			int nr = i - ap[val][1];
			int nr2 = sol - ap[val][0];
			int nr3 = (n - i) / nr;
			
			sol += nr2 * nr3;
			i += nr * nr3;
			
			for (++i; i <= n; ++i)
			{
				t4 = (t3 + t2 * t1) % 10;
				sol += t4;
				
				t1 = t2;
				t2 = t3;
				t3 = t4;
			}
			
			g << sol;
			g.close ();
			return 0;
		}
	}
	
	g << sol;
	
	g.close ();
	return 0;
}