Cod sursa(job #460891)

Utilizator DraStiKDragos Oprica DraStiK Data 4 iunie 2010 15:58:48
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define DIM 1005

int viz[DIM],sum[DIM];
int n,a,b,c,d;

inline int trans (int a,int b,int c)
{
    return c+b*10+a*100;
}

void solve ()
{
    int i,m,lg;

    sum[1]=(a%=10);
    sum[2]=a+(b%=10);
    sum[3]=a+b+(c%=10);
    viz[trans (a,b,c)]=1;
    for (i=4; i<=n; ++i)
    {
        d=(c+a*b)%10;
        a=b; b=c; c=d;
        sum[i]=sum[i-1]+d;
        if (viz[trans (a,b,c)])
        {
			m=n-viz[trans (a,b,c)]+1;
            lg=i-viz[trans (a,b,c)]-2;
            printf ("%d",sum[viz[trans (a,b,c)]-1]+(m/lg)*(sum[i-3]-sum[viz[trans (a,b,c)]-1])+sum[viz[trans (a,b,c)]+(m%lg)-1]-sum[viz[trans (a,b,c)]-1]);
            return ;
        }
        else
            viz[trans (a,b,c)]=i-2;
    }
    printf ("%d",sum[n]);
}

int main ()
{
    freopen ("koba.in","r",stdin);
    freopen ("koba.out","w",stdout);

    scanf ("%d%d%d%d",&n,&a,&b,&c);
    if (n==1)
        printf ("%d",a%10);
    else if (n==2)
        printf ("%d",a%10+b%10);
    else if (n==3)
        printf ("%d",a%10+b%10+c%10);
    else
        solve ();

    return 0;
}