Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.
Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).
Input
- Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
- Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).
Output
- Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.
Example
Test 1
Input
7 6
1 2 4 3 4 5 3
Output
4
Bình luận
This comment is hidden due to too much negative feedback. Click here to view it.
hint
bài này có 2 cách:
-Cách 1 dành cho ai làm trâu ta sẽ duyệt mảng như bình thường và xét trường hợp nếu như biến ta cứ cho là n mà bằng với tổng mảng a[i]+a[j] thì ta sẽ đăng biến đếm lên cách này thì sẽ dẫn đến bị tle
-Cách 2 thì dùng hàm chặt có sẵn là ac
Spoiler Alert
Lưu ý trường hợp 2 * Ai = x :>
a ơi pas e chạy dc mà nộp bị lỗi phân khúc do sao ạ
hint 1 là nhanh nhất r
hmm
Spoiler Alert
Hint 1
Hint 2
Hint 3
Reference AC code | O(n log n) time | O(n) auxiliary space | STL, Combinatorics