Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #807334) | Monitorul de evaluare | Cod sursa (job #3324435)
// programul numara triunghiurile folosind 2 for-uri + cautare binara
#include <bits/stdc++.h>
using namespace std;
int v[801];
int n;
// caut binar ultima poz unde v[k] <= valoare
int bs_ultima_poz(int valoare) {
int st = 0, dr = n - 1, rasp = -1;
while (st <= dr) {
int mid = st + (dr - st) / 2;
if (v[mid] <= valoare) {
rasp = mid;
st = mid + 1;
} else {
dr = mid - 1;
}
}
return rasp; // -1 inseamna ca nu exista
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v, v + n);
long long nr = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int suma = v[i] + v[j];
int k = bs_ultima_poz(suma); // ultima poz valida
if (k > j) {
nr += (k - j); // betisoarele j+1, j+2 ..., k sunt valide
}
}
}
cout << nr;
return 0;
}