Pagini recente » Cod sursa (job #1109128) | Cod sursa (job #3178533) | Cod sursa (job #1734913) | Cod sursa (job #1457163) | Cod sursa (job #812479)
Cod sursa(job #812479)
#include <stdio.h>
#include <bitset>
#define hash_size 1100
using namespace std;
int t1,t2,t3,tn,nr,sol,s[hash_size], hash[hash_size],N;
void read_data()
{
FILE*f = fopen("koba.in","r");
fscanf(f,"%d%d%d%d",&N,&t1,&t2,&t3);
fclose(f);
}
void small_data()
{
t1 %= 10;
t2 %= 10;
t3 %= 10;
}
void next_term()
{
t1 = t2;
t2 = t3;
t3 = tn;
}
void make_nr()
{
nr = t3 * 100 + t2 * 10 + t1;
}
int main()
{
read_data();
small_data();
make_nr();
hash[nr] = 3;
sol += t1;
sol += t2;
sol += t3;
s[3] = sol;
int i,per_length,rest;
for(i=4;i<=N;++i)
{
tn = (t3 + t2*t1)%10;
sol += tn;
s[i] = sol;
next_term();
small_data();
make_nr();
if(hash[nr])//s-a format o perioada
{
per_length = i - hash[nr];//lungimea perioadei
rest = N - i;//cat a mai ramas din sir
sol += (rest/per_length)*(s[i] - s[hash[nr]]);//adun suma dintr-o perioada de rest/per_length ori, adica de cate ori mai intra o perioada intrega in sir
sol += s[hash[nr] + rest%per_length] - s[hash[nr]];//mai adaug la solutie cat a mai ramas(suma primelor rest%per_length elemente)
i = N+1;
}
else
{
hash[nr] = i;
}
}
FILE*g = fopen("koba.out","w");
fprintf(g,"%d\n",sol);
fclose(g);
return 0;
}