Lật Kèo Thằng Tèo (bản khó)
View as PDFMột ngày xấu trời nọ, Tí nghĩ ra một trò chơi như sau: cho một số nguyên dương ~n~, trong một thao tác, ta có thể chọn một chữ số bất kì của ~n~, tạm gọi chữ số đó là ~d~, và trừ ~n~ đi một lượng là ~d~. Ví dụ: ~n = 27~, thì ta có thể chọn số ~2~ hoặc số ~7~, và trừ ~n~ đi ~2~ hoặc ~7~. Trò chơi sẽ kết thúc khi ~n = 0~. Tí thấy trò chơi này rất vui, nên đã đem trờ chơi này để so tài với Tèo, xem ai có thể đưa số ~n~ về ~0~ trong ít lượt thao tác nhất. Đáng tiếc thay, trong ~8~ tỉ người trên Trấi Đất, Tí lại chọn trúng Tèo - một pro-gamer, giỏi vô đối ở những trò chơi não to như thế này, nên dù Tí là người sáng lập ra trò chơi, cậu vẫn bại trận thảm hại dưới tay Tèo. Không chịu gục ngã trước số phận, Tí muốn lật kèo Tèo, từ đó thoát ra khỏi kiếp cơ hàn, vươn lên từ đáy xã hội. Tuy nhiên, là một con người tài trí có hạn, thủ đoạn vô biên, Tí đã không chăm chỉ học hành, phát triển tư duy, mà thay vào đó đã thuê bạn viết chương trình cố vấn cho anh ấy, mách nước đi tối ưu tiếp theo. Nhưng kế hoạch của Tí đã đổ bể! Vì hầu bao có hạn, anh ấy chỉ có thể trả tiền để bạn viết chương trình tính xem với số ~n~ bất kì, cần tối thiểu bao nhiêu thao tác để có thể kết thúc trò chơi. Liệu bạn có thể viết chương trình hỗ trợ anh ấy trong công cuộc lật kèo thằng Tèo?
Input:
Dòng thứ nhất chứa số nguyên dương ~n~.
Output:
In ra kết quả của bài toán trên.
Sample Input:
27
Sample Output:
5
Giải thích test mẫu: Tí có thể thực hiện ~5~ thao tác sau để kết thúc trò chơi:
- ~n = 27~, chọn số ~7~ và trừ ~n~ đi ~7~.
- ~n = 20~, chọn số ~2~ và trừ ~n~ đi ~2~.
- ~n = 18~, chọn số ~8~ và trừ ~n~ đi ~8~.
- ~n = 10~, chọn số ~1~ và trừ ~n~ đi ~1~.
- ~n = 9~, chọn số ~9~ và trừ ~n~ đi ~9~. ~n = 0~ nên trò chơi kết thúc.
Có thể chứng minh rằng không tồn tại dãy thao tác để có thể đưa ~n~ về ~0~ trong ít hơn ~5~ thao tác. Như vậy, đáp án là ~5~.
- Subtask 1: (12.5% số điểm): ~n \leq 10^6~.
- Subtask 2: (87.5% số điểm): ~n \leq 10^{18}~.
Comments
=)) nguồn bài : TMK mới đúng nha thầy
ok em