Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - Making Triangle Editorial by evima

Since $$N \leq 100$$, it is possible try all tuples $$(i, j, k)$$ and check if it forms a triangle. Three sides of length $$a$$, $$b$$ and $$c$$ forms a triangle if and only if

• $$a + b > c$$,
• $$b + c > a$$ and
• $$c + a > b$$,

so you can solve this problem by checking the following two conditions: - $$L_i$$, $$L_j$$ and $$L_k$$ are all different, and - $$L_i$$, $$L_j$$ and $$L_k$$ satisfies the condition above.

The total time complexity is $$O(N^3)$$.

Just an aside, if you sort $$L$$ firsthand and assume that they satisfy $$L_1 \leq L_2, \cdots, \leq L_N$$, the only triangular inequality that has to be check is that $$L_i + L_j > L_k$$.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int N;
cin >> N;
vector<int> vec(N);
for (int i = 0; i < N; ++i) cin >> vec[i];
sort(vec.begin(), vec.end());

int ans = 0;

for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k < j; ++k) {
if (vec[k] != vec[j] and vec[i] != vec[j] and
vec[k] + vec[j] > vec[i]) {
ans++;
}
}
}
}

cout << ans << endl;

return 0;
}


posted:
last update: