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.

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.