Cod sursa(job #858267)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 ianuarie 2013 18:59:40
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#define Nmax (1<<10)
#define Nr(i) (100*T[Norm(i)]+10*T[Norm(i-1)]+T[Norm(i-2)])
#define Norm(i) ((i-1)%4)
using namespace std;

int N,T[4],Sum,V[Nmax],Hash[Nmax];

void Solve() {

    int i,L,Rest;

    T[0]%=10;
    T[1]%=10;
    T[2]%=10;

    Sum=T[0]+T[1]+T[2];
    Hash[Nr(3)]=3;
    V[3]=Sum;

    for(i=4;i<=N;i++) {

        T[Norm(i)]=(T[Norm(i-1)]+T[Norm(i-2)]*T[Norm(i-3)])%10;
        Sum+=T[Norm(i)];
        V[i]=Sum;

        if(Hash[Nr(i)]) {

            L=i-Hash[Nr(i)];
            Rest=N-i;

            Sum+=(V[i]-V[Hash[Nr(i)]])*(Rest/L);
            Sum+=V[Hash[Nr(i)]+Rest%L]-V[Hash[Nr(i)]];

            break;

            }
        else
            Hash[Nr(i)]=i;

        }

}
void Read() {

    ifstream in("koba.in");
    in>>N>>T[0]>>T[1]>>T[2];
    in.close();

}
void Write() {

    ofstream out("koba.out");
    out<<Sum<<'\n';
    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}