Pagini recente » Cod sursa (job #2027690) | Cod sursa (job #1996247) | Cod sursa (job #3312526) | Cod sursa (job #3315165) | Cod sursa (job #3324450)
// programul numara triunghiurile folosind 2 for-uri + cautare binara
#include <bits/stdc++.h>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
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() {
fin >> 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
}
}
}
fout << nr;
return 0;
}