Lật Kèo Thằng Tèo

View as PDF
Submit solution
Points: 200.00
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
LeKienThanh
Problem type
Allowed languages
C, C++, GAS64, Java, Pascal, Perl, PHP, Python, Sed, TCL, Text

Mộ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 ~T~ (~T \leq 10^6~), là số lượng truy vấn Tí muốn hỏi chương trình.

~T~ dòng tiếp theo, mỗi dòng chứa một số ~n~.

Output:

In ra kết quả của bài toán trên với mỗi truy vấn.

Sample Input:
5
6
9
27
69
420
Sample Output:
1
1
5
12
72

Giải thích test mẫu: Ở truy vấn thứ ~3~, Tí có thể thực hiện ~5~ thao tác sau để kết thúc trò chơi:

  1. ~n = 27~, chọn số ~7~ và trừ ~n~ đi ~7~.
  2. ~n = 20~, chọn số ~2~ và trừ ~n~ đi ~2~.
  3. ~n = 18~, chọn số ~8~ và trừ ~n~ đi ~8~.
  4. ~n = 10~, chọn số ~1~ và trừ ~n~ đi ~1~.
  5. ~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: (50% số điểm): ~n \leq 10^6~, với mọi truy vấn.
  • Subtask 2: (50% số điểm): ~n \leq 5 * 10^7~, với mọi truy vấn.

Comments

Please read the guidelines before commenting.