|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
C - Counting substhreengs
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Substrings are strings formed by choosing a subset of contiguous characters from a string. This is well known. A little more obscure is the definition of substhreengs. A substhreeng is a substring which complies to the following additional requirements:
1. It is non-empty, and composed entirely of base $10$ digits.
2. Interpreted in base $10$ (allowing extra leading zeros), the resulting integer is a multiple of $3$.
For instance, the string $\texttt{130a303}$ contains $9$ substhreengs: the substhreeng $\texttt{3}$ three times, the substhreengs $\texttt{30}$ and $\texttt{0}$ twice each, and the substhreengs $\texttt{303}$ and $\texttt{03}$ once each. The substring $\texttt{30a3}$ is not a substhreeng because it is not composed entirely of base $10$ digits, while the substring $\texttt{13}$ is not a substhreeng because $13$ is not a multiple of $3$.
Notice that two substhreengs are considered different if they are different in length or start at a different position, even if the selected characters are the same.
Given a string, you are asked to count the number of substhreengs it contains.
Input
The input consists of a single line that contains a non-empty string $S$ of at most $10^6$ characters. Each character of $S$ is either a digit or a lowercase letter.
Output
Output a line with an integer representing the number of substhreengs contained in $S$.
Sample test(s)
Input
130a303
Output
9
Input
0000000000
Output
55
Input
icpc2014regional
Output
2