Preparando MOJI

Foreigner

1000ms 262144K

Description:

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:

  • all integers from $$$1$$$ to $$$9$$$ are inadequate;
  • for an integer $$$x \ge 10$$$ to be inadequate, it is required that the integer $$$\lfloor x / 10 \rfloor$$$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $$$\lfloor x / 10 \rfloor$$$ have number $$$k$$$ in this order. Then, the integer $$$x$$$ is inadequate only if the last digit of $$$x$$$ is strictly less than the reminder of division of $$$k$$$ by $$$11$$$.

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.

Input:

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.

Output:

In the only line print the number of substrings of $$$s$$$ that form an inadequate number.

Sample Input:

4021

Sample Output:

6

Sample Input:

110

Sample Output:

3

Note:

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).

Informação

Codeforces

Provedor Codeforces

Código CF1142D

Tags

dp

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 09:46:13

Relacionados

Nada ainda