Đếm số cặp phần tử có tổng bằng s
Trong một dãy ngắn, câu hỏi "có bao nhiêu cặp số cộng lại đúng bằng một mốc cho trước"
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
Trong một dãy ngắn, câu hỏi "có bao nhiêu cặp số cộng lại đúng bằng một mốc cho trước" xuất hiện khi kiểm tra hai món hàng vừa đủ một hạn mức, hoặc hai chỉ số bù trừ nhau. Vì dãy rất ngắn, ta cứ thử hết mọi cặp là xong.
Yêu cầu
Cho n số nguyên và một giá trị s. Hãy đếm số cặp chỉ số (i, j) với i < j sao cho a[i] + a[j] == s. Mỗi cặp được tính đúng một lần, thứ tự của hai phần tử trong cặp không quan trọng.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin theo đúng định dạng trên và in ra stdout một số nguyên duy nhất là số cặp tìm được.
Input
- Dòng 1: hai số nguyên n và s (1 <= n <= 20, -20000 <= s <= 20000).
- Dòng 2: n số nguyên a1 a2 ... an (-10000 <= ai <= 10000).
Output
Một số nguyên duy nhất: số cặp (i, j) với i < j thoả a[i] + a[j] == s.
Ràng buộc
- n nhỏ, nên vòng lặp đôi O(n * n) là hoàn toàn đủ.
- Dãy không được sắp xếp sẵn và có thể chứa giá trị trùng nhau, thậm chí giá trị âm.
- Mỗi bộ dữ liệu chạy trong 1 giây.
Ví dụ 1
Input
5 6
1 2 3 4 5
Output
2
Ví dụ 2
Input
4 4
2 2 2 2
Output
6
Giải thích
Dữ liệu vào:
Hai cặp thoả mãn là (1, 5) và (2, 4) (đang ghi giá trị), nên in ra 2.
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.
