Fișierul intrare/ieșire	secv9.in, secv9.out	Sursă	Olimpiada pe scoala clasele a 11-a si a 12-a, 2018
Autor	Victor Manz	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.05 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Secv9 (clasele 11 și 12)

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₁, a₂, .., 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).

Date de intrare

Fișierul de intrare secv9.in va conține un șir de N cifre nenule, reprezentând numărul X.

Date de ieșire

În fișierul de ieșire secv9.out va fi afișat numărul cerut.

Restricții

• 1 ≤ N ≤ 100 000

Exemplu

Explicație

...