Quy Hoạch Động Chữ Số
Xem PDF
Điểm:
100
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Hàm \(F(a)\) với \(a\) là một số nguyên dương được định nghĩa đệ quy như sau:
- Nếu \(a < 10, F(a) = a\).
- Nếu \(a > 9, F(a) = F\)(tổng các chữ số của a).
Ví dụ, \(F(91) = F(10) = 1\).
cần các bạn đếm số lượng số \(x\) trong đoạn \([l, r]\) mà \(F(x) = 9\).
Dễ dàng nhận thấy bài toán này có thể giải được bằng quy hoạch động chữ số cơ bản. Hãy thể hiện trình độ bản thân với nhé.
Input
-
Dòng đầu tiên chứa 1 số nguyên dương \(Q\) là lượng câu hỏi.
-
\(Q\) dòng tiếp theo chứa, mỗi dòng chứa 1 cặp số nguyên dương \(l, r\) biểu thị một đoạn.
Output
- \(Q\) dòng, mỗi dòng là số lượng số \(x\) tương ứng.
Scoring
-
Subtask \(1\) (\(50\%\) số điểm): \(Q \leq 100\) và \(1\) \(\leq\) \(l\) \(\leq\) \(r\) \(\leq\) \(10^{5}\).
-
Subtask \(1\) (\(50\%\) số điểm): \(Q \leq 10^{5}\) và \(1\) \(\leq\) \(l\) \(\leq\) \(r\) \(\leq\) \(10^{9}\).
Example
Test 1
Input
2
1 2
1 9 Output
0
1Note
- Không có số \(x\) trong đoạn \([1, 2]\) mà \(F(x) = 9\).
- Chỉ có \(x = 9\) thuộc đoạn \([1, 9]\) và \(F(x) = 9\).
Bình luận
Hint ko cần quy hoạch động
Ta thấy các số chia hết cho 9 khi tính tổng đến khi là một chữ số thì đều ra 9
VD:
S(n) là tổng các chữ số của n
S(11187) = S(18) = S(9)
Khi ta thay hàm S(n) thành F(n) thì cơ chế cũng giống như vậy
=> Đếm các số chia hết cho 9 từ l đến r :)
P/S : Mình lớp 6 nên giải thích khá khó hiểu :v
Code Python (Không nên chép
)