Fişierul intrare/ieşire:secv9.in, secv9.outSursăOlimpiada pe scoala clasele a 11-a si a 12-a, 2018
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.05 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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ă 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 a1, a2, .., an este un subşir format din elemente aflate pe poziţii consecutive în şir: ai, ai+1, .., ai+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
  • pentru 30% din teste 1 ≤ N ≤ 100
  • pentru 50% din teste 1 ≤ N ≤ 1 000

Exemplu

secv9.insecv9.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici