Số cặp

Xem PDF

Tất cả bài nộp

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

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

Test 2

Input

7
6 2 4 2 4 3 4

Output

Bình luận

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()

11 bình luận nữa