Bài 21: Tricount

Đăng bởi Admin

Tháng 10 10, 2022

Share0

Tweet0

Pin0

Tham khảo tại https://freecontest.net/

https://chuyenhalong.ucode.vn/problems/tricount-119290

Cho $N$ thanh sắt, thanh sắt thứ $i$ có độ dài là $A_i$ . Đếm số lượng bộ ba $(i, j, k)(1 \leq i<j<k \leq N)$ sao cho ba thanh sắt có độ dài lần lượt là $A_i, A_j$ và $A_k$ tạo thành mọ̄t tam giác.

Đầu vào
– Dòng đầu tiên chứa số nguyên dương $N$ tương ứng với số lượng thanh sắt.
– Dòng thứ hai chứa $N$ số nguyên, số thứ $i$ có giá trị là $A_i$ tương ứng với độ dài thanh sắt thứ $i$

Đầu ra
– In ra một số nguyên duy nhất là số lượng bộ ba $(i, j, k)$ thỏa mãn điều kiện đề bài.

Giải thích
Những bộ ba thỏa mãn đề bài lần lượt là $(2,3,4),(2,4,5)$ và $(3,4,5)$ .

Ràng buộc
Trong tất cả các test, $0 \leq A_i \leq 1000$ .
– Subtask 1 (20\%): $1 \leq N \leq 500$ .
– Subtask 2 (40\%): $1 \leq N \leq 3000$ .
– Subtask 3 (40\%): $1 \leq N \leq 8000$ .