h2. Solutia 1 (neoptima)

h2(#koba). 'Koba':problema/koba

O solutie neoptima ar fi parcurgerea de la 1 la N si adaugarea fiecarei cifre cerute la suma. Acest lucru se face folosind doar ultimele cifre din numere, pentru a nu implementa pe numere mari, cu formula T~i~=(T~i-1~+T~i-2~*T~i-3~) % 10. Complexitatea acestei solutii este O(n).

h3. Solutia 1 (neoptima)

h2. Solutia 2

O solutie neoptima ar fi parcurgerea de la $1$ la $N$ si adaugarea fiecarei cifre cerute la suma. Acest lucru se face folosind doar ultimele cifre din numere, pentru a nu implementa pe numere mari, cu formula $T{~i~}=(T{~i-1~}+T{~i-2~}*T{~i-3~}) % 10$. Complexitatea acestei solutii este $O(N)$.

Pentru o solutie optima, se observa ca, de la un moment dat, sirul devine periodic. Fie numarul abc care reprezinta 3 cifre a, b si, respectiv, c.
Tinem un vector in care A[abc] va reprezenta pozitia pe care a aparut tripletul a, b, c in sirul pe care l-am construit pana la momentul respectiv. Parcurgand cu un indice i de la 1 la N si adunand in suma S cifrele folosite pana la momentul actual, daca la un moment dat, un triplet a, b, c va aparea pentru a doua oara, facem suma cifrelor ( notata cu SUM ) de la ultima aparitie a celor 3 cifre pana la momentul actual si memoram in M numarul de cifre din aceasta suma (i-A[abc]+1). In acest moment, stim suma cifrelor pana la pasul i. Acum trebuie aflata suma cifrelor de la i+1 la N. Pentru a afla acesta suma, scadem din n pe i (pentru a afla suma cifrelor de dupa i) si vedem de cate ori intra in "noul" n acea secventa "periodica" si adunam (N/M)*Sum la S. Pana acum am calculat suma cifrelor pana la cel mai mare multiplu al lui M mai mic decat N. De aici mai adaugam la S primele N%M cifre din partea periodica.

h3. Solutia 2
 
Pentru o solutie optima, se observa ca, de la un moment dat, sirul devine periodic. Fie numarul $abc$ care reprezinta $3$ cifre $a, b$ si, respectiv, $c$.
Tinem un vector in care $A[abc]$ va reprezenta pozitia pe care a aparut tripletul $a, b, c$ in sirul pe care l-am construit pana la momentul respectiv. Parcurgand cu un indice $i$ de la $1$ la $N$ si adunand in suma $S$ cifrele folosite pana la momentul actual, daca la un moment dat, un triplet $a, b, c$ va aparea pentru a doua oara, facem suma cifrelor (notata cu $Sum$) de la ultima aparitie a celor $3$ cifre pana la momentul actual si memoram in $M$ numarul de cifre din aceasta suma $(i-A[abc]+1)$. In acest moment, stim suma cifrelor pana la pasul $i$. Acum trebuie aflata suma cifrelor de la $i+1$ la $N$. Pentru a afla acesta suma, scadem din $N$ pe $i$ (pentru a afla suma cifrelor de dupa $i$) si vedem de cate ori intra in "noul" $N$ acea secventa "periodica" si adunam $(N/M)*Sum$ la $S$. Pana acum am calculat suma cifrelor pana la cel mai mare multiplu al lui $M$ mai mic decat $N$. De aici mai adaugam la $S$ primele $N%M$ cifre din partea periodica.