Quy Hoạch Động Chữ Số

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
ami
Dạng bài
Đ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\).

ami 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 ami 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
1
Note
  • 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


  • 2
    tknhatbm    11:26 a.m. 11 Tháng 2, 2023 ← đã chỉnh sửa
    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 )
    Python
    q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    kq = r // 9 - l // 9
    if l % 9 == 0: kq += 1
    print(kq)
    2 phản hồi