e-olymp
Змагання

Dynamic Programming - Linear

Видалення цифр

Задано натуральне число n. На кожному кроці дозволено відняти від числа будь яку цифру, яка присутня у заданому числі.

За яку найменшу кількість кроків можна отримати число 0?

Вхідні дані

Одне натуральне число n (1n106).

Вихідні дані

Виведіть найменшу кількість кроків, за які можна отримати число 0.

Пояснення

Для n = 27 оптимальним розв'язком буде 2720181090.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
27
Вихідні дані #1
5