Cod sursa(job #809609)

Utilizator andunhillMacarescu Sebastian andunhill Data 8 noiembrie 2012 18:48:55
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#include<iostream>
#include<iomanip>
#include<ctime>
using namespace std;

clock_t start=clock();

ifstream f("koba.in");
ofstream g("koba.out");

int N, M;

int T1, T2, T3, T4;
long long sum[1000001];
int poz[1000];

int main()
{   int i, j, p;
    long long Sm = 0, S = 0;

    f>>N;
    f>>T1>>T2>>T3;

    T1 %= 10; T2 %= 10; T3 %= 10;
    sum[1] = T1;
    sum[2] = T1 + T2;
    sum[3] = sum[2] + T3;
    poz[T1 * 100 + T2 * 10 + T3] = 3;
    for(i = 4; i <= N; i++)
    {   T4 = (T3 + T2 * T1) % 10;
        sum[i] = sum[i - 1] + T4;
        p = poz[T2 * 100 + T3 * 10 + T4];

        if(!p)
            poz[T2 * 100 + T3 * 10 + T4] = i;
        else
        {   M = i - p;
            Sm = sum[i - 1] - sum[p - 1];
            S = sum[i - 1];
            N = N - i + 1;

            S += N / M * Sm;
            S += sum[p + N % M - 1] - sum[p - 1];
            break;
        }
        T1 = T2;
        T2 = T3;
        T3 = T4;
    }

    g<<S;
    cout << 1.0*(clock()-start)/(1.0*CLOCKS_PER_SEC) << '\n';
    f.close();
    g.close();
    return 0;
}