Đếm cặp đôi (HSG'20)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

admin

Dạng bài

Đ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

Bình luận

def count_pairs(n, x, A):
count = 0
frequency = {}

for num in A:
    target = x - num
    if target in frequency:
        count += frequency[target]

    if num in frequency:
        frequency[num] += 1
    else:
        frequency[num] = 1

return count

n, x = map(int, input().split())
A = list(map(int, input().split()))

result = count_pairs(n, x, A)
print(result)

16 bình luận nữa