Cod sursa(job #996616)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 12 septembrie 2013 13:36:06
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <bitset>

using namespace std;

bitset<1005> viz;
int unde[1005];
int sum[1005];

int main()
{
    ifstream fin("koba.in");
    ofstream fout("koba.out");

    int n,i,t1,t2,t3,copie,aux;
    fin>>n>>t1>>t2>>t3;

    t1%=10;
    t2%=10;
    t3%=10;
    //cout<<t1<<' '<<t2<<' '<<t3<<' ';
    aux=100*t1+10*t2+t3;
    viz[aux]=1;
    sum[1]=t1;
    sum[2]=t1+t2;
    sum[3]=t1+t2+t3;
    unde[aux]=3;
    int total=0;
    bool stop=false;
    for(i=4;i<=n;i++)
    {
        copie=t3;
        t3=((t1*t2)%10+t3)%10;
        t1=t2;
        t2=copie;
        //cout<<t3<<' ';
        sum[i]=sum[i-1]+t3;
        aux=100*t1+10*t2+t3;
        if(viz[aux])
        {
            //cout<<"HOP! "<<i-unde[aux]<<endl;
            total+=sum[unde[aux]-3];
            n-=(unde[aux]-3);
            total+=(n/(i-unde[aux])*(sum[i-3]-sum[unde[aux]-3]));
            n%=(i-unde[aux]);
            total+=(sum[unde[aux]-3+n]-sum[unde[aux]-3]);
            stop=true;
            break;
        }
        viz[aux]=1;
        unde[aux]=i;
    }
    if(stop)
        fout<<total<<'\n';
    else
        fout<<sum[n]<<'\n';
    fin.close();
    fout.close();
    return 0;
}