Cod sursa(job #2875682)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 22 martie 2022 10:04:42
Problema Koba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> presum;

int freq[10][10][10];

int buildPresum(int t1, int t2, int t3) {
  int cycle = 0;
  t1 = t1 % 10;
  t2 = t2 % 10;
  t3 = t3 % 10;
  while(freq[t1][t2][t3] == 0) {
    //cout << t1 << ' ' << t2 << ' ' << t3 << ' ' << cycle << '\n';
    int add;
    if(presum.size() > 0){
      add = presum[presum.size() - 1] + t1;
    }else{
      add = t1;
    }

    presum.push_back(add);
    freq[t1][t2][t3] = cycle;
    cycle++;
    int t4 = (t3 + t1 * t2) % 10;
    t1 = t2;
    t2 = t3;
    t3 = t4;
  }
  //cout << t1 << ' ' << t2 << ' ' << t3 << '\n';
  //cout << freq[t1][t2][t3] << '\n';
  return freq[t1][t2][t3];
}

int main() {

  int n, t1, t2, t3, cycle;
  in >> n >> t1 >> t2 >> t3;
  n--;
  int cycleStart = buildPresum(t1, t2, t3);
  if(n < presum.size()) {
    out << presum[n];
  }else {
    n -= presum.size();
    int ans = presum[presum.size() - 1];
    int cycleLength = presum.size() - cycleStart;
    int cycleSum, cycleFinish;
    if(cycleStart == 0){
      cycleFinish = presum[n % cycleLength + cycleStart];
      cycleSum = presum[presum.size() - 1];
    }else {
      cycleFinish = presum[n % cycleLength + cycleStart] - presum[cycleStart - 1];
      cycleSum = presum[presum.size() - 1] - presum[cycleStart - 1];
    }
    /*
    cout << presum[0] << ' ';
    for(int i = 1;i < presum.size();i++) {
      cout << presum[i] - presum[i - 1] << ' ';
    }
    cout << '\n';
    for(int i = 0;i < presum.size();i++) {
      cout << presum[i] << ' ';
    }
    cout << '\n' << presum[presum.size() - 1] << ' ' << n << ' ' << cycleStart << ' ' << cycleLength << ' ' << cycleSum << ' ' << cycleFinish << '\n';
    */
    ans += (n / cycleLength) * cycleSum + cycleFinish;
    out << ans;
  }
  return 0;
}