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

Xem PDF
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 
4

Bình luận


  • 0
    thinhec12012007    9:51 p.m. 24 Tháng 4, 2024

    Mọi người có thể tham khảo code :

    include <bits/stdc++.h>

    using namespace std;
    map<int,int>mp;

    define ll long long

    int n,k,x;
    ll res=0;
    int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    int tam;
    for(int i=1;i<=n;i++) {
    cin>>x;
    mp[x]++;
    tam=k-x;
    if(k-x!=x)
    res+=mp[k-x];

    }
ll gan=mp[k/2];
if(gan>=2) gan--;
else gan=0;

cout<<res+(gan*(gan+1)/2);
return 0;

    }

      • 9 bình luận nữa