Recurenta

Pentru a afla termenul de indice n al sirului D vom calcula pe rand toate valorile lui D_i pentru k ≤ i ≤ n. O prima solutie tine un vector de intregi pe 64 de biti si pentru a calcula valoarea lui D_i itereaza pe rand peste toate valorile D_j, i - k ≤ j ≤ i-1, adunandu-le.
Aceasta solutie are complexitate O(n*k) si functioneaza pentru n foarte mic, solutia ia 30 de puncte. O solutie asemanatoare dar care foloseste adunarea pe numere mari va lua 60 de puncte. Se observa ca nu avem nevoie decat de ultimii k termeni ai sirului D pentru a determina valoarea unui termen, astfel putem optimiza memoria folosita de la O(N * nr_mari) la O(K * nr_mari). De asemeni nu este nevoie sa calculam suma ultimilor k termeni la fiecare pas, pentru ca D_i+1 = 2 * D_i - D_i-k. Folosind aceasta relatie de recurenta complexitatea algoritmului este de O(N * nr_mari) si obtine 100 de puncte. Pentru ca solutia sa intre in memorie se va utiliza optimizarea prezentata mai sus sau numerele mari vor fi implementate folosind o baza mare (10⁹)