Hạ số bằng chữ số

Bối cảnh và bài toán

Một bộ đếm đang ở giá trị n. Ở mỗi thao tác, bạn được chọn một chữ số khác 0 đang xuất hiện trong giá trị hiện tại và trừ chữ số đó khỏi bộ đếm.

Yêu cầu

Tìm số thao tác ít nhất để đưa bộ đếm về 0.

Input

Một dòng chứa n.

Output

In số thao tác ít nhất.

Ràng buộc

• 1 <= n <= 10^6

Chấm điểm

Ví dụ 1

Input

1

Output

1

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

9

Output

1

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Removing Digits. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.