cs_100 Đếm số tam giác đều
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
501M
Input:
stdin
Output:
stdout
Dạng bài
cs_100 Đếm số tam giác đều
Cho dãy số nguyên a không âm. Nhiệm vụ của bạn là đếm có bao nhiêu bộ (i,j, k) sao cho ai, aj, a_k tạo thành tam giác đều.
Dữ liệu vào:
- Gồm 2 dòng. Dòng thứ nhất chứa số nguyên n. Dòng tiếp theo chứa n số nguyên a_i
Dữ liệu ra:
- Gồm 1 số nguyên duy nhất, là kết quả tính toán.
Ví dụ:
INPUT:
4
2 1 2 2
OUTPUT:
1
Bình luận
include<bits/stdc++.h>
using namespace std;
long long toHop3(long long f) { return f * (f - 1) * (f - 2) / 6; }
int main() { int n; cin >> n; long long a[1000005]; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); long long result = 0; long long count = 1; for (int i = 1; i < n; i++) { if (a[i] == a[i - 1]) { count++; } else { if (count >= 3) { result += toHop3(count); } count = 1; } } if (count >= 3) { result += toHop3(count); } cout << result; return 0; }