Trọng số đoạn
Xem dạng PDF
Mã bài:
ib_sum2
Điểm:
2,5 (OI)
Giới hạn thời gian:
0.5s
Giới hạn bộ nhớ:
125M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Cái đẹp trong mắt mỗi người là khác nhau và Gấu cũng thế, Gấu say mê với những con số đẹp (tất nhiên là cũng có con gái đẹp). Con số theo Gấu là đẹp được định nghĩa như sau:
Trọng số một số "đẹp" nguyên dương $X$, kí hiệu $f(X)$ được tính:
- Nếu $X$ có một chữ số trong biểu diễn thập phân thì $f(X) = X$.
- Nếu $X$ có nhiều hơn một chữ số thì $f(X)$ là tổng hai chữ số lớn nhất và lớn nhì của $f(X)$.
Ví dụ $f(3) = 3, f(152) = 5 + 2 = 7$.
Trọng số một đoạn $[L, R]$ là tổng trọng số của $f(X)$ mà $L \leq X \leq R$.
Để phục vụ cho việc gì đó, mỗi ngày trong ~Q~ ngày Gấu cần phải tính trọng số đoạn ~[L, R]~. Bạn hãy giúp Gấu nhé.
Dữ liệu vào
- Dòng đầu tiên gồm số nguyên ~Q~ ~(1 \leq Q \leq 10^5)~.
- ~Q~ dòng sau, mỗi dòng gồm ba số nguyên ~L, R~ ~(1 \leq L \leq R \leq 10^{18})~.
Dữ liệu ra
Gồm ~Q~ dòng là đáp án của ~Q~ câu hỏi chia dư cho $10^9 + 2709$.
Ví dụ
Input
3
1 20
100 1000
1 100270908
Output
102
10576
563685276
Tính điểm
- Subtask 1 (30% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^6~.
- Subtask 2 (40% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^{18}~.
- Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.
Bình luận
cảm ơn anh tuấn anh vì đã fix lại bài này:)
lúc đầu chả hiểu sao sai