Rezolvare PBinfo #2283

Se consideră un șir S de cifre nenule. O secvență a șirului S este o succesiune de cifre din S care apar pe poziții consecutive. Un număr n asociat unei secvențe din S este numărul în baza 10 care se formează cu toate cifrele din secvența respectivă, în ordinea în care apar în aceasta.

Un număr n se numește caraghios dacă este egal cu pătratul sumei cifrelor lui n.

Cerința

Dându-se un șir S de cifre nenule, să se determine câte dintre secvențele din S au numere asociate caraghioase.

Date de intrare

Fișierul de intrare caraghios.in conține pe prima linie șirul S de cifre nenule.

Date de ieșire

Fișierul de ieșire caraghios.out va conține pe prima linie numărul de secvențe din S care au asociate numere caraghioase.

Restricții și precizări

• Șirul S va conține maxim 1.000.000 de cifre

Exemplu:

caraghios.in

28113

caraghios.out

3

Explicație

Toate secvențele lui S sunt: 2, 28, 281, 2811, 28113, 8, 81, 811, 8113, 1, 11, 113, 1, 13, 3
Există 3 secvențe care au asociate numere caraghioase: 81, 1, 1
81 = (8+1)*(8+1), 1 = 1*1, 1 = 1*1