Số cặp

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên dương \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n.\)

Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? \((\)Bao nhiêu cặp \(a_i\) \(=\) \(a_j\) với \(i\) \(\neq\) \(j,\) \((ai,\) \(aj)\) và \((aj,\) \(ai)\) chỉ được tính là \(1\) cặp\().\)

Input

  • Dòng thứ nhất là chiều dài \(n\) của mảng \((1\) \(\leq\) \(n\) \(\leq\) \(10^5).\)
  • Dòng thứ hai gồm \(n\) số nguyên \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n\) \((1\) \(\leq\) \(a_i\) \(\leq\) \(10^5),\) mỗi số cách nhau một khoảng trắng.

Output

  • Là số nguyên xác định số lượng các cặp bằng nhau.

Example

Test 1

Input 
5
8 2 9 8 1
Output 
1

Test 2

Input 
7
6 2 4 2 4 3 4
Output 
4

Bình luận


  • 0
    thuannguyen1972dn    7:14 p.m. 2 Tháng 5, 2024

    code python:def chap(k, n):
    if k == 0 or k == n:
    return 1
    elif k == 1:
    return n
    else:
    return chap(k - 1, n - 1) + chap(k, n - 1)

    def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    n = int(data[0])  # Đọc giá trị của n
a = list(map(int, data[1:n+1]))  # Đọc dãy a

# Sử dụng dictionary để đếm số lần xuất hiện của từng phần tử trong a
mp = {}
for num in a:
    if num in mp:
        mp[num] += 1
    else:
        mp[num] = 1

ans = 0
# Duyệt qua từng cặp (key, value) trong dictionary mp
for key, value in mp.items():
    if value == 2:
        ans += 1
    elif value > 2:
        ans += chap(2, value)

print(ans)

    if name == "main":
    main()


    • 0
      khaidadao    11:10 p.m. 10 Tháng 4, 2024

      Để tối ưu hóa bài này thì nên sài đệ quy về : chập (2, số lượng phần tử) ; )
      Code mẫu ac : https://www.ideone.com/gngGZL


      • 32
        SPyofgame    6:26 p.m. 5 Tháng 6, 2020

        Spoiler Alert

        Hint

        Gọi M[x] = số lần xuất hiện của x trong mảng a

        Kết quả bài toán là res = Σ(x ∈ a){ M[x] * (M[x] - 1) / 2 }

        1 phản hồi