Cod sursa(job #919396)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:06:50
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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;
}