== include(page="template/taskheader" task_id="secv9") ==
Aritmel este pasionat de aritmetică și de multe ori inventează probleme din acest domeniu, pe care apoi se străduiește să le și rezolve. De data aceasta însă și-a cam prins urechile și vă cere ajutorul, pentru că problema la care s-a gândit pare mult prea dificilă atunci când numerele prelucrate sunt foarte mari.
Despre ce este vorba: de curând Aritmel a învățat că numerele naturale sunt divizibile cu 9 dacă și numai dacă au suma cifrelor divizibilă cu 9. Imediat și-a pus următoarea întrebare: dacă am un număr foarte mare X, câte numere divizibile cu 9 pot să extrag din el în condițiile în care aleg doar cifre aflate pe poziții consecutive în X?
Scrieți un program care să citească o secvență de cifre nenule reprezentând un număr care poate fi foarte mare și să calculeze câte subsecvențe ale acesteia corespund unor numere divizibile cu 9.
Aritmel este pasionat de aritmetică și de multe ori inventează probleme din acest domeniu, pe care apoi se străduiește să le și rezolve. De data aceasta însă și-a cam prins urechile și vă cere ajutorul, pentru că problema la care s-a gândit pare mult prea dificilă pentru el atunci când numerele prelucrate sunt foarte mari.
Despre ce este vorba: de curând Aritmel a învățat că numerele naturale sunt divizibile cu *9* dacă și numai dacă au suma cifrelor divizibilă cu *9*. Imediat și-a pus următoarea întrebare: dacă am un număr foarte mare *X*, câte numere divizibile cu *9* pot să extrag din el în condițiile în care aleg doar cifre aflate pe poziții consecutive în *X*?
Scrieți un program care să citească un șir de cifre *nenule* reprezentând un număr care poate fi foarte mare și să calculeze câte subsecvențe ale acestuia corespund unor numere divizibile cu *9*. O subsecvență a unui șir *a[~1~]*, *a[~2~]*, .., *a[~n~]* este un subșir format din elemente aflate pe poziții consecutive în șir: *a[~i~]*, *a[~i+1~]*, .., *a[~i+k-1~]* unde *k* este un număr natural (secvența poate avea și lungimea *1*).
h2. Date de intrare
Fișierul de intrare $secv9.in$ ...
Fișierul de intrare $secv9.in$ va conține un șir de $*N*$ cifre nenule, reprezentând numărul $*X*$.
h2. Date de ieșire
În fișierul de ieșire $secv9.out$ ...
În fișierul de ieșire $secv9.out$ va fi afișat numărul cerut.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* pentru 30% din teste $1 ≤ N ≤ 100$
* pentru 50% din teste $1 ≤ N ≤ 1 000$
h2. Exemplu
table(example).
|_. secv9.in |_. secv9.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|_. secv9.in |_. secv9.out |_. Explicații |
| 9919
| 4
| Secvențele formate din prima cifră, cea formată din a doua cifră, cea formată din a patra cifră și cea formată din primele 2 cifre corespund unor numere divizibile cu 9.
|
| 3815265
| 3
| Secvențele formate din a doua și a treia cifră (81), cea formată din a doua, a treia, a patra, a cincea, a șasea și a șaptea cifră (815265) și
cea formată din a patra, a cincea, a șasea și a șaptea cifră (5265) corespund unor numere divizibile cu 9.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="secv9") ==
