Cod sursa(job #138613)

Utilizator za_wolfpalianos cristian za_wolf Data 18 februarie 2008 22:12:52
Problema Koba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#define NMAX 100010
long long i,q,d,n,a,b,c,m,aa,bb,cc,s,p;
long long x[NMAX],y[NMAX];
int main()
{
	freopen("koba.in","r",stdin);
	freopen("koba.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	if (n==1)
	{
		printf("%lld\n",a%10);
		return 0;
	}	else
	if (n==2)
	{
		printf("%lld\n",a%10+b%10);
		return 0;
	}	else
	if (n==3)
	{
		printf("%lld\n",a%10+b%10+c%10);
		return 0;
	}
	aa=a%10;
	bb=b%10;
	cc=c%10;
	a=aa;
	b=bb;
	c=cc;
	s=a%10+b%10+c%10;
	m=3;
	q=1;
	x[a*100+b*10+c]=1;
	y[1]=a;
	y[2]=a+b;
	y[3]=a+b+c;

	while (q/*&&m<n*/)
	{
		d=(c+a*b)%10;
		s+=d;
		a=b;
		b=c;
		c=d;
		m++;
		if (x[a*100+b*10+c]==0)
			x[a*100+b*10+c]=m;
		else
		q=0;
		y[m]=s;
	}

	i=x[a*100+b*10+c];
//	if (m<n)
	{
	s=y[i]+(((n-i)/(m-i))*(y[m]-y[i]));
	m=m-i;
	n=n-i;

	for (i=1;i<=3;i++)
	{
		d=(c+a*b)%10;
		a=b;
		b=c;
		c=d;
	}

/*	if (n%m==1)
		s+=a;
	if (n%m==2)
		s+=a+b;
	if (n%m==3)
		s+=a+b+c; */

	if (n%m>3)
	{

		p=4;
		s+=a+b+c;
		while (p<=n%m)
		{
			d=(c+a*b)%10;
			s+=d;
			a=b;
			b=c;
			c=d;
			p++;
		}
	}
	}
	printf("%lld\n",s);
	return 0;
}