← 返回题目列表

AtCoder · abc407_c

E. 安全 2

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

分数: 300 点

问题陈述

在AtCoder Inc.的入口处,有一个特殊的密码输入设备。 该设备由一个显示一根字符串的屏幕和两个按钮组成。

让 t 是屏幕上显示的字符串。 最初, t 是空字符串。按下按钮会发生变化 t 如下:

  • 按下 按钮 A 附加 0 到年底 t.
  • 按下 按钮 B 替换中的每个数字 t 与下一个数字:用于数字 0 通过 8 下一位是其值较大的一位 1;之后的下一个数字 9 is 0.

例如,如果 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.

  1. 按按钮 A。 t 变为 0.
  2. 按按钮 B。 t 变为 1.
  3. 按按钮 A。 t 变为 10.
  4. 按按钮 B。 t 变为 21.

不可能获得 21 按下次数少于四次,因此输出 4.


示例输入 2

407

示例输出 2

17

示例输入 3

2025524202552420255242025524

示例输出 3

150