BS10 - Tìm kiếm nhị phân 10: 3 cạnh tam giác

Đề bài

Một hôm, Phát và Quân rảnh rỗi nên lấy một hộp diêm ra chơi. Trong hộp có \(n\) que diêm, que thứ \(i\) có độ dài nguyên dương \(a_i\).

Phát đố Quân chọn ra ba que diêm khác nhau để xếp thành một hình tam giác.

Ba que diêm có độ dài \(a_i\), \(a_j\), \(a_k\), với \(i\), \(j\), \(k\) đôi một khác nhau, có thể xếp thành một tam giác nếu tổng độ dài của hai que bất kỳ luôn lớn hơn độ dài của que còn lại.

Hãy xác định có bao nhiêu bộ ba que diêm khác nhau có thể xếp thành một hình tam giác.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) — số que diêm trong hộp.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) — độ dài của các que diêm.

Dữ liệu ra

In ra một số nguyên là số bộ ba que diêm khác nhau có thể xếp thành một hình tam giác.

Hai bộ được xem là khác nhau nếu chúng chọn các bộ chỉ số khác nhau.

Ràng buộc

• \(1 < n \le 5000\).
• \(1 \le a_i \le 10^9\).

Subtask

• Subtask 1 (30%): \(n \le 100\).
• Subtask 2 (30%): \(100 < n \le 1000\).
• Subtask 3 (40%): \(1000 < n \le 5000\).

5
4 3 1 5 7

3

Giải thích

Có \(3\) bộ ba que diêm có thể xếp thành tam giác:

• \((4,3,5)\);
• \((4,5,7)\);
• \((3,5,7)\).

Vì vậy, kết quả cần in ra là \(3\).