Cặp số bằng nhau

Xem dạng PDF

Gửi bài giải

Điểm: 0,01 (OI)
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 256M
Input: CSBN.inp
Output: CSBN.out

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bình là học sinh có đam mê với các con số. Một hôm Bình ngồi viết ra 1 dãy số nguyên bất kì và nhận thấy có nhiều số nguyên có giá trị bằng nhau. Bình muốn biết dãy số vừa viết ra có bao nhiêu cặp số có giá trị bằng nhau nên nhờ các bạn học sinh giỏi Tin lập trình giúp.

Yêu cầu: Cho ~N~ số nguyên dương lần lượt là ~a_1~, ~a_2~, ..., ~a_N~. Hãy giúp Bình xác định có bao nhiêu cặp số bằng nhau (~a_i = a_j~ với ~i < j~ được tính là ~1~ cặp).

Input

Từ tệp văn bản CSBN.INP gồm ~2~ dòng:

  • Dòng thứ nhất là số nguyên ~N~ (~1 \le N \le 10^7~).

  • Dòng thứ hai gồm ~N~ số ~a_1~, ~a_2~, ..., ~a_N~ (~1 \le a_i \le 10^9~).

Output

Đưa tệp văn bản CSBN.OUT chứa số cặp bằng nhau.

Sample Input 1

5
4 5 4 6 1

Sample Output 1

1

Sample Input 2

7
7 8 6 8 6 3 6

Sample Output 2

4

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    khanhdzvcl  đã bình luận lúc 18, Tháng 4, 2025, 1:12

    Bài này dùng unordered_map sẽ không bị TLE 😊


  • -1
    tranbaphu098  đã bình luận lúc 17, Tháng 4, 2025, 11:50

    sos


  • -1
    tranbaphu098  đã bình luận lúc 16, Tháng 4, 2025, 12:29

    def giaibaitoan(): try: with open("cSBN.INP", "r") as fin: nstr = fin.readline().strip() n = int(nstr) astr = fin.readline().strip().split() a = [int(x) for x in a_str]

        counts = {}
        for x in a:
            counts[x] = counts.get(x, 0) + 1
    
        so_cap = 0
        for count in counts.values():
            if count > 1:
                so_cap += count * (count - 1) // 2
    
        with open("CSBN.OUT", "w") as f_out:
            f_out.write(str(so_cap))
    
    except FileNotFoundError:
        print("Không tìm thấy tệp cSBN.INP")
    except ValueError:
        print("Định dạng đầu vào không hợp lệ")
    

    if name == "main": giaibaitoan()


  • -3
    Gilderoy  đã bình luận lúc 11, Tháng 4, 2025, 14:14

    include <bits/stdc++.h>

    define GILDEROY

    typedef long long ll;

    using namespace std;

    void open_file(){ #ifdef GILDEROY freopen ("CSBN.inp", "r", stdin); freopen ("CSBN.out", "w", stdout); #endif }

    void solve(){ int n; cin >> n; vector<int> a(n); for(int i=0; i<n;i++) { cin >> a[i]; } unordered_map<int, ll> b; for(int i=0;i<n;i++) { b[a[i]]++; } int cnt = 0; for(auto it : b) { // cout << it.first << " " << it.second << "\n"; if(it.second >= 2) { cnt += ((it.second*(it.second-1))/2); } } cout << cnt; }

    int main(){ iosbase::syncwithstdio(0); cin.tie(nullptr); cout.tie(nullptr); openfile(); solve(); return 0; }


  • -3
    vylun271027  đã bình luận lúc 9, Tháng 4, 2025, 12:21

    include <bits/stdc++.h>

    using namespace std; <!--ifstream fi("BAI5.INP");--> <!--ofstream fo("BAI5.OUT");--> int main(){ int n; cin >> n; vector<int>a(n); for(int i=0;i<n;i++){ cin>>a[i]; } unordered_map<int,int> b; for(int i=0;i<n;i++){ b[a[i]]++; } int cnt = 0; for(auto it: b){ if(it.second == 2){ cnt++; } } cout <<cnt; return 0; }


  • 6
    quangthenpc  đã bình luận lúc 5, Tháng 4, 2025, 6:58

    !SPOILER!

    Dùng công thức tổ hợp để tính.

    Ta có công thức tổ hợp để tính số cặp tạo thành được từ n lần xuất hiện của a_i là: $$ C_n^k = \frac{n!}{(n - k)! . k!} $$.

    Nhận thấy rằng trong bài toán này, k = 2, nên công thức tổ hợp chỉ còn là: $$ C_n^2 = \frac{n * (n - 1)}{2} $$ Với n là số lần xuất hiện của một số trong mảng.

    Code: https://onlinegdb.com/VK77shNe6