Đếm số phần tử bằng x trong một đoạn
Đếm số lần một giá trị xuất hiện trong một đoạn con là câu hỏi hay gặp khi kiểm tra dữ liệu.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Đếm số lần một giá trị xuất hiện trong một đoạn con là câu hỏi hay gặp khi kiểm tra dữ liệu. Với mảng chỉ có vài chục phần tử, cách làm gọn gàng và an toàn nhất là duyệt thẳng các vị trí trong đoạn rồi so sánh với giá trị cần tìm, không cần cấu trúc dữ liệu đặc biệt nào.
Yêu cầu
Cho mảng a gồm n số nguyên đánh số từ 1 đến n. Với mỗi câu hỏi (l, r, x), hãy đếm xem trong đoạn a[l], a[l+1], ..., a[r] có bao nhiêu phần tử đúng bằng x. Cả hai đầu l và r đều nằm trong đoạn được xét.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Mỗi câu hỏi in đúng một số nguyên trên một dòng riêng.
Input
- Dòng thứ nhất: số nguyên n là số phần tử (1 <= n <= 20, mảng rất nhỏ).
- Dòng thứ hai: n số nguyên a[1] đến a[n], cách nhau bởi dấu cách (|a[i]| <= 10000).
- Dòng thứ ba: số nguyên q là số câu hỏi (1 <= q <= 10).
- q dòng tiếp theo: mỗi dòng ba số nguyên l, r, x theo thứ tự đó, cách nhau bởi dấu
cách (1 <= l <= r <= n, |x| <= 10000).
Output
- q dòng, dòng thứ i là số phần tử bằng x trong đoạn của câu hỏi thứ i.
Ràng buộc
- 1 <= n <= 20, 1 <= q <= 10, |a[i]| <= 10000, |x| <= 10000.
- Mảng nhỏ nên mỗi câu hỏi có thể duyệt thẳng từ l đến r.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
6
1 2 1 3 1 2
3
1 6 1
2 5 2
3 3 1
Output
3
1
1
Ví dụ 2
Input
3
7 7 7
2
1 3 7
1 3 5
Output
3
0
Giải thích
Với dữ liệu vào:
Câu hỏi 1 6 1 đếm được ba số 1, câu hỏi 2 5 2 đếm được một số 2, câu hỏi 3 3 1 đếm được một số 1, nên kết quả là:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
