CSES - Removing Digits | Loại bỏ chữ số

Xem PDF
Tác giả:
Flower_On_Stone , kitsune , Elektrikar
Dạng bài
Điểm: 1300 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một số nguyên \(n\). Ở mỗi bước, bạn có thể trừ \(n\) đi một lượng bằng một trong các chữ số của nó.

Cần bao nhiêu bước để làm cho \(n\) bằng \(0\)?

Input

  • Gồm một dòng duy nhất chứa số nguyên \(n\).

Output

  • In ra một số nguyên duy nhất là số bước tối thiểu cần dùng.

Constraints

  • \(1 \leq n \leq 10 ^ 6\)

Example

Sample input

27

Sample output

5

Note

Một giải pháp tối ưu là \(27 \to 20 \to 18 \to 10 \to 9 \to 0\).

Bình luận