DDP01. Tổng chữ số bằng S

Đề bài

Cho L, R, S. Đếm số x trong [L, R] có tổng chữ số đúng bằng S.

Dữ liệu vào

L R S

Dữ liệu ra

Một số nguyên là số lượng số thỏa mãn.

Ví dụ

Input:
0 99 2
Output:
3

Input:
1 1000 10
Output:
63

Input:
123 4567 15
Output:
343

Chia sub

• Sub 1: Giới hạn nhỏ, có thể kiểm tra bằng duyệt để học sinh hiểu đề.

• Sub 2: Giới hạn trung bình, cần bắt đầu dùng Digit DP.

• Sub 3: Giới hạn lớn, bắt buộc tối ưu trạng thái.

• Sub 4: Giới hạn rất lớn, cần code Digit DP chuẩn.

Thuật toán chi tiết

dp(pos, sum, tight). Khi thử chữ số d, chuyển sang sum+d. Đáp án đoạn là solve(R)-solve(L-1).

Khung chung: xây hàm solve(N) đếm/tính trên đoạn [0, N], sau đó lấy solve(R) - solve(L-1) nếu đề có đoạn [L, R]. Với số lớn dạng chuỗi, xử lý trực tiếp trên chuỗi.