Pagini recente » Cod sursa (job #3363628) | Cod sursa (job #3362345) | Cod sursa (job #3362103) | Cod sursa (job #3363799) | Cod sursa (job #3363797)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 800;
int v[MAXN];
int main()
{
FILE *fin, *fout;
int i, j, n, rez, k;
fin = fopen("nrtri.in", "r");
fscanf(fin, "%d", &n);
for (i = 0; i < n; i++) {
fscanf(fin, "%d", &v[i]);
}
fclose(fin);
sort(v, v + n);
//o(n^2) cu 2 pointers, calculez numarul de triunghiuri care nu sunt valide
rez = n * (n - 1) * (n - 2) / 6;
for (i = 0; i < n; i++) {
j = i + 1;
k = j + 1;
while (j < n && k < n) {
while (k < n && v[i] + v[j] >= v[k]) {
k++;
}
rez -= (n - k);
j++;
}
}
fout = fopen("nrtri.out", "w");
fprintf(fout, "%d\n", rez);
fclose(fout);
return 0;
}