← 返回题目列表

Codeforces · 1142/D

D. 外国人

中文机器翻译题面 查看原题

在世界各地旅行时,您注意到如果看到您是外国人,许多商店老板会将价格提高到不合适的价格。

您定义的数量不足如下:

- 从 $$$1$$$ 到 $$$9$$$ 的所有整数都是不够的;
- 如果整数 $$$x \ge 10$$$ 不充分,则要求整数 $$$\lfloor x / 10 \rfloor$$$ 不充分,但这不是唯一的条件。让我们对所有不足的整数进行排序。让 $$$\lfloor x / 10 \rfloor$$$ 按此顺序具有数字 $$$k$$$。那么,仅当 $$$x$$$ 的最后一位数字严格小于 $$$k$$$ 除以 $$$11$$$ 的提示时,整数 $$$x$$$ 是不够的。

这里 $$$\lfloor x / 10 \rfloor$$$ 表示 $$$x/10$$$ 向下舍入。

因此,如果 $$$x$$$ 是按升序排列的第 $$$m$$$ 不足数,并且 $$$m$$$ 给出除以 $$$11$$$ 后的余数 $$$c$$$,则整数 $$$10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ 为不足,而整数 $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$$$ 并不不足。

前几个不充足的整数是 $$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$$$。之后,由于 $$$4$$$ 是第四个不足整数,因此 $$$40, 41, 42, 43$$$ 是不足的,而 $$$44, 45, 46, \ldots, 49$$$ 是不不足的;由于 $$$10$$$ 是第 $$$10$$$ 个不足数,因此整数 $$$100, 101, 102, \ldots, 109$$$ 都是不足的。由于 $$$20$$$ 是第 $$$11$$$ 个不足的数字,因此 $$$200、201、202、\ldots、209$$$ 都不是不足的。

您写下了一次旅行中看到的所有价格。不幸的是,所有整数都连接在一个大数字字符串 $$$s$$$ 中,并且您丢失了相邻整数之间的界限。您现在感兴趣的是结果字符串中构成数量不足的子字符串的数量。如果某个子字符串在不同位置出现多次,则其所有出现都将单独计数。

输入

唯一一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$),仅由数字组成。保证 $$$s$$$ 的第一位数字不为零。

输出

在唯一的一行中打印 $$$s$$$ 中形成不足数量的子字符串的数量。

示例

输入 #1

4021

输出 #1

6

输入 #2

110

输出 #2

3

注意

在第一个示例中,字符串中的不足数字是 $$$1, 2, 4, 21, 40, 402$$$。

在第二个示例中,字符串中的不足数字是 $$$1$$$ 和 $$$10$$$,并且 $$$1$$$ 出现两次(在第一个位置和第二个位置)。