|Codeforces Round #549 (Div. 1)|
Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.
You define inadequate numbers as follows:
Here $$$\lfloor x / 10 \rfloor$$$ denotes $$$x/10$$$ rounded down.
Thus, if $$$x$$$ is the $$$m$$$-th in increasing order inadequate number, and $$$m$$$ gives the remainder $$$c$$$ when divided by $$$11$$$, then integers $$$10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ are inadequate, while integers $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$$$ are not inadequate.
The first several inadequate integers are $$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$$$. After that, since $$$4$$$ is the fourth inadequate integer, $$$40, 41, 42, 43$$$ are inadequate, while $$$44, 45, 46, \ldots, 49$$$ are not inadequate; since $$$10$$$ is the $$$10$$$-th inadequate number, integers $$$100, 101, 102, \ldots, 109$$$ are all inadequate. And since $$$20$$$ is the $$$11$$$-th inadequate number, none of $$$200, 201, 202, \ldots, 209$$$ is inadequate.
You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string $$$s$$$ and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.
The only line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$), consisting only of digits. It is guaranteed that the first digit of $$$s$$$ is not zero.
In the only line print the number of substrings of $$$s$$$ that form an inadequate number.
In the first example the inadequate numbers in the string are $$$1, 2, 4, 21, 40, 402$$$.
In the second example the inadequate numbers in the string are $$$1$$$ and $$$10$$$, and $$$1$$$ appears twice (on the first and on the second positions).