Cod sursa(job #171700)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 4 aprilie 2008 20:53:03
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#define N 1000
int v[N],per[N];
int ok,n,i,sper=0,suma=0,poz;
void scan()
{
	freopen("koba.in", "r",stdin);
	freopen("koba.out", "w",stdout);
	scanf("%d", &n);
	scanf("%d%d%d", &v[1],&v[2],&v[3]);
	v[1]%=10; v[2]%=10; v[3]%=10;
}
inline int gaseste()
{
	for(int k=3;k<=i-3;++k)
		if(v[k]==v[i] && v[k-1]==v[i-1] && v[k-2]==v[i-2])
			{poz=k-3; return 1;}
	return 0;
}
void prelucreaza()
{
	for(int k=1;k<=poz;++k)
		suma+=v[k];
	for(int k=poz+1;k<=i-3;++k)
		per[ ++per[0] ]=v[k];
}
void solve()
{
	if(n<500)
	{
		for(i=4;i<=n;++i)
			v[i]=(v[i-1]+v[i-2]*v[i-3])%10;
		for(int i=1;i<=n;++i)
			suma+=v[i];
		printf("%d\n",suma);
		return;
	}	
	for(i=4;i<=n;++i)
	{
		v[i]=(v[i-1]+v[i-2]*v[i-3])%10;
		if(gaseste() )
			{ prelucreaza(); break; }
	}
	for(int j=1;j<=per[0];++j)
		sper+=per[j];
	suma+=sper*((n-poz)/per[0]);
	for(int i=1;i<=(n-poz)%per[0];++i)
		suma+=per[i];
	printf("%d\n",suma);
}
int main()
{
	scan();
	solve();
	return 0;
}