Hướng dẫn giải

Đếm số cách chọn ba số hạng (ba chỉ số ~i < j < k~) làm ba cạnh của một tam giác đều (TGD = tam giác đều).

Lưu ý về đề: câu chữ trong đề chỉ ghi "ba cạnh của một tam giác" (thiếu chữ "đều"), nhưng tên bài TGD, ví dụ và toàn bộ test đều thống nhất với cách hiểu tam giác đều. Ở ví dụ, dãy ~1, 2, 2, 2, 2, 10, 99, -9, 9~ cho kết quả ~4~: đó chính là ~\binom{4}{3} = 4~ cách chọn ba số ~2~. Nếu là tam giác bất kỳ thì còn các bộ ~(1, 2, 2)~, ~(2, 9, 10)~... và kết quả lớn hơn nhiều. Vậy ta đếm các bộ ba có ~a_i = a_j = a_k > 0~ (cạnh phải dương, số ~0~ hoặc số âm không phải độ dài cạnh).

Sub 1: Vét cạn mọi bộ ba — ~O(n^3)~, dùng khi ~n \le 100~

Duyệt mọi bộ ba chỉ số ~i < j < k~, đếm các bộ có ~a_i = a_j = a_k > 0~. Nếu chỉ nộp sub này: đúng 10/20 test.

Sub 2: Sắp xếp và đếm nhóm — ~O(n \log n)~

Sau khi sắp xếp, mỗi nhóm giá trị dương bằng nhau gồm ~c~ phần tử cho ~\binom{c}{3} = c(c-1)(c-2)/6~ bộ ba. Cộng lại, dùng ~long long~ vì đáp án tới ~1,6 \cdot 10^{10}~. Nếu chỉ nộp sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

Main đọc ~n~ và dãy (máy chấm dùng đọc/ghi chuẩn); ~n \le 100~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

#include <bits/stdc++.h>
using namespace std;

int n;
long long a[100005];

// Lưu ý: dữ liệu mẫu và test của máy chấm chỉ khớp khi đếm bộ ba số dương BẰNG NHAU
// (tam giác đều - TGD), không khớp với "tam giác bất kỳ" như chữ trong đề.

// Sub 1: vét cạn mọi bộ ba chỉ số i < j < k, O(n^3), dùng khi n <= 100
void sub1() {
    long long cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
                if (a[i] > 0 && a[i] == a[j] && a[j] == a[k]) cnt++;
    printf("%lld\n", cnt);
}

// Sub 2: sắp xếp, mỗi nhóm giá trị dương bằng nhau có c phần tử cho C(c,3) bộ ba. O(n log n)
void sub2() {
    sort(a, a + n);
    long long cnt = 0;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && a[j] == a[i]) j++;
        long long c = j - i;
        if (a[i] > 0) cnt += c * (c - 1) * (c - 2) / 6;
        i = j;
    }
    printf("%lld\n", cnt);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    if (n <= 100) sub1();
    else sub2();
    return 0;
}