Mã nghi vấn (Tuyển sinh 10 tỉnh Khánh Hòa năm học 2026-2027)
kh_ts10_2627_05 1000 ms 512 MB
Nội dung bài tập

Trong buổi tuyên truyền về an toàn trên không gian mạng, nhà trường giới thiệu một hệ thống nhận diện các số điện thoại có dấu hiệu quảng cáo hoặc lừa đảo. Để bảo vệ quyền riêng tư cá nhân, hệ thống này chỉ lưu trữ 4 chữ số cuối của mỗi số điện thoại, gọi là mã đuôi. Một mã đuôi (gồm đúng 4 chữ số) được gọi là mã nghi vấn nếu nó thỏa mã đồng thời 3 điều kiện sau:

1/ Chữ số đầu tiên là 2 hoặc 0;

2/ Chữ số cuối cùng là 2 hoặc 6;

3/ Hai chữ số ở giữa giống nhau.

Ví dụ: 2556, 0006, 2112 là các mã nghi vấn; còn 2229, 9129 không là mã nghi vấn.

Hệ thống thu thập \(n\) số điện thoại, các số điện thoại được đánh số từ 1 đến \(n\). Số điện thoại thứ \(i\ (1 \leq i \leq n)\) có mã đuôi là \(s_{i}\). Hệ thống ghi nhận \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L,\ R\).

Yêu cầu: Cho \(n,\ s_{1},s_{2},\ldots,s_{n}\) và \(q\). Ứng với mỗi truy vấn, hãy đếm số lượng mã nghi vấn trong dãy \(s_{L},\ s_{L + 1},\ \ldots,s_{R}\).

Dữ liệu vào:

- Dòng 1 ghi hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 10^{5};1 \leq q \leq 5 \times 10^{3})\);

- Dòng 2 ghi \(n\) mã đuôi \(s_{1},s_{2},\ldots,s_{n}\);

- \(1\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(L,\ R\ \ (1 \leq L \leq R \leq n)\), biểu diễn một truy vấn.

Kết quả: Ghi trên \(q\) dòng:

- Dòng thứ \(i\ (1 \leq i \leq q)\) ghi một số nguyên là số lượng mã nghi vấn ứng với truy vấn \(i\).

Ràng buộc:

- Subtask 1 (10% số điểm): \(q = 1\);

- Subtask 2 (10% số điểm): \(n \leq 10^{3};q \leq 10^{3}\);

- Subtask 3 (80% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input Output

8 4

2556 2229 0006 2112 9129 2002 0116 1236

1 4

2 8

5 7

4 8

3

4

2

3

Giải thích: Các mã nghi vấn trong danh sách đã cho là: 2556, 0006, 2112, 2002, 0116;

- Truy vấn 1: xét các phần tở từ 1 đến 4, có 3 mã nghi vấn là 2556, 0006, 2112;

- Truy vấn 2: xét các phần tử từ 2 đến 8, có 4 mã nghi vấn là 0006, 2112, 2002, 01116;

- Truy vấn 3: xét các phần tử từ 5 đến 7, có 2 mã nghi vấn là 2002, 0116;

- Truy vấn 4, xét các phần tử từ 4 đến 8, có 3 mã nghi vấn là 2112, 2002, 0116;

Nộp bài
Bạn cần đăng nhập để nộp bài. Đăng nhập
Lịch sử nộp bài của bạn
Bạn chưa nộp bài tập này.
Thống kê bài nộp
3
Tổng lượt nộp
Đang chờ chấm
0
Đang chấm
0
Chấp nhận
2
Sai kết quả
1
Quá thời gian
0
Lỗi biên dịch
0
Lỗi thực thi
0
Lỗi hệ thống
0
Vượt giới hạn bộ nhớ
0
Vượt giới hạn output
0
Các bài tập cùng đề thi