Đếm số có tổng chữ số bằng S

Buổi 05 — Hàm & Đệ quy Mathematics
Points
43
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho ba số nguyên $L, R, S$. Hãy sử dụng quy hoạch động chữ số bằng đệ quy có nhớ (Digit DP) để đếm xem trong đoạn $[L, R]$ có bao nhiêu số nguyên có tổng các chữ số bằng đúng $S$.

Dữ liệu vào

Một dòng chứa ba số nguyên $L, R, S$.

Dữ liệu ra

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

Ví dụ
Input Output
1 20 5 2
10 99 18 1
Giới hạn

$1 \le L \le R \le 10^{18}$, $1 \le S \le 162$.

Draft saved