TS10 Điện Biên 2026 - Đếm cặp
Xem dạng PDFGắn kết hai số nguyên là việc được thể hiện bởi chuỗi công việc sau:
Đầu tiên, chuyển cả hai số nguyên đó thành chuỗi.
Tiếp theo, gắn kết hai chuỗi đó thành một.
Cuối cùng, chuyển chuỗi mới thành một số nguyên.
Ví dụ, gắn kết hai số ~123~ và ~45~ là ~CONCAT(123, 45) = 12345~, gắn kết hai số ~1~ và ~3~ là ~CONCAT(1, 3) = 13~.
Bạn được cho một dãy gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ và hai số ~L, R~.
Yêu cầu: Hãy đếm xem có bao nhiêu cặp số ~(i, j)~ trong đó (~1 \le i, j \le N~) mà ~L \le CONCAT(a_i, a_j) \le R~.
Input
Dòng thứ nhất chứa một số nguyên ~T~ (~1 \le T \le 10^4~) - số lượng test. Mỗi test được mô tả như sau:
Dòng đầu tiên chứa ba số nguyên ~N, L, R~ (~2 \le N \le 10^5, 1 \le L \le R \le 10^{15}~).
Dòng tiếp theo chứa ~N~ số nguyên, số thứ ~i~ có giá trị ~a_i~ (~1 \le a_i \le 10^9~).
Tổng của ~N~ trong các test không vượt quá ~10^6~.
Output
Gồm ~T~ dòng, mỗi dòng in ra một số nguyên duy nhất là số lượng cặp ~(i, j)~ thỏa mãn yêu cầu trên.
Scoring
| Subtasks | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~1 \le T \le 10^2; 2 \le N \le 10^2, 1 \le L \le R \le 10^{10}~ |
| 2 | ~70\%~ | ~1 \le T \le 10^4; 2 \le N \le 10^5, 1 \le L \le R \le 10^{15}~ |
Sample Input 1
3
3 10 52
3 5 7
3 58 100
4 2 3
5 28 102
3 2 1 9 10
Sample Output 1
3
0
11
Notes
Ở ví dụ thứ nhất:
~(i=1, j=1): CONCAT(a_1, a_1) = 33~ và ~10 \le 33 \le 52~.
~(i=1, j=2): CONCAT(a_1, a_2) = 35~ và ~10 \le 35 \le 52~.
~(i=1, j=3): CONCAT(a_1, a_3) = 37~ và ~10 \le 37 \le 52~.
Ở ví dụ thứ hai: Không có cặp số nào có thể tạo ra số nguyên lớn hơn
Bình luận
đề kỳ kỳ ta, sao cảm giác nó bị thiếu gì á :)))?
con cat