URI Online Judge | 1745

Contando Substhreengs

Por Pablo Ariel Heiber, Universidad de Buenos Aires AR Argentina

Timelimit: 1

Substrings são strings formadas pela escolha de um subconjunto de caracteres contíguos a partir de uma string. Isto é bem conhecido. Um pouco mais obscura é a definição de substhreengs. A substhreeng é uma substring que cumpre com os seguintes requisitos adicionais:

1. É não-vazio, e composto inteiramente de dígitos de base 10.

2. Interpretada na base 10 (permitindo zeros extras), o inteiro resultante é um múltiplo de 3.

Por exemplo, a string "130a303" contém 9 substhreengs: o substhreeng "3" três vezes, os substhreengs "30" e "0" duas vezes cada, e os substhreengs "303" e "03", uma vez cada. A substring "30a3" não é um substhreeng porque não é inteiramente composto por dígitos de base 10, enquanto a substring "13" não é um substhreeng porque 13 não é um múltiplo de três.

Note que dois substhreengs são consideradas diferentes se eles são diferentes em comprimento ou começar numa posição diferente, mesmo se os caracteres selecionados são os mesmos.

Dado uma string, você está convidado a contar o número de substhreengs que ela contém.

Entrada

A entrada consiste de uma única linha que contém uma string não-vazia S de, no máximo, 10 6 caracteres. Cada personagem do S ou é um dígito ou uma letra minúscula.

Saída

Apresente uma linha com um inteiro que representa o número de substhreengs contido em S.

Exemplos de Entrada Exemplos de Saída

130a303

9

0000000000

55

icpc2014regional

2