1483 - Gắn kết số

Tạo bởi: GV. Bùi Phú Khuyên

Mô tả yêu cầu

Trong một buổi học lập trình, thầy Khuyên yêu cầu sinh viên viết một chương trình thực hiện việc gắ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ố 12345CONCAT(123, 45) = 12345, gắn kết hai số 13CONCAT(1, 3) = 13.

Bạn được cho một dãy gồm N số nguyên a_1, a_2,..., a_n, và hai số L, R. Hãy đếm xem có bao nhiêu cặp số (i, j) trong đó (1 \leq i, j \leq N)L \leq CONCAT(a_i, a_j) \leq R.

Dữ liệu vào

  • Dòng thứ nhất chứa một số nguyên T (1 \leq T \leq 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 \leq N \leq 10^5, 1 \leq L \leq R \leq 10^{15}).
    • Dòng tiếp theo chứa N số nguyên, số thứ i có giá trị a_i (1 \leq a_i \leq 10^7).

Tổng của N trong các test không vượt quá 10^6

Dữ liệu ra

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.

Ví dụ

Dữ liệu vào Sao chép
3
3 10 52
3 5 7
3 58 100
4 2 3
5 28 102
3 2 1 9 10
Dữ liệu ra Sao chép
3
0
11

Gợi ý/Hướng dẫn

  • Ở ví dụ thứ nhất:

    • (i = 1, j = 1): CONCAT(a_1, a_1) = 3310 \leq 33 \leq 52.
    • (i = 1, j = 2): CONCAT(a_1, a_2) = 3310 ≤ 35 ≤ 52.
    • (i = 1, j = 3): CONCAT(a_1, a_3) = 3310 ≤ 37 ≤ 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 58.

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB