分数: 300 点
问题陈述
在AtCoder Inc.的入口处,有一个特殊的密码输入设备。 该设备由一个显示一根字符串的屏幕和两个按钮组成。
让 t 是屏幕上显示的字符串。 最初, t 是空字符串。按下按钮会发生变化 t 如下:
- 按下 按钮 A 附加
0到年底 t. - 按下 按钮 B 替换中的每个数字 t 与下一个数字:用于数字
0通过8下一位是其值较大的一位 1;之后的下一个数字9is0.
例如,如果 t is 1984 并按下按钮 A, t 变为 19840;如果然后按下按钮 B, t 变为 20951.
给你一个字符串 S。从空字符串开始,按按钮零次或多次,直到 t 与 S。找出所需的最少按钮按下次数。
约束
- S 是一个由以下组成的字符串
0,1,2,3,4,5,6,7,8,和9. - 1 \le |S| \le 5 \times 10^{5},其中 |S| 的长度 S.
输入
输入由标准输入按以下格式给出:
S
输出
输出答案。
示例输入 1
21
示例输出 1
4
以下按下顺序使 t 等于 21.
- 按按钮 A。 t 变为
0. - 按按钮 B。 t 变为
1. - 按按钮 A。 t 变为
10. - 按按钮 B。 t 变为
21.
不可能获得 21 按下次数少于四次,因此输出 4.
示例输入 2
407
示例输出 2
17
示例输入 3
2025524202552420255242025524
示例输出 3
150