Pagini recente » Autentificare | Atasamentele paginii Profil Marius_Gheorghe | Cod sursa (job #3357706) | Cod sursa (job #437734) | Cod sursa (job #3324468)
#include <bits/stdc++.h>
#define NMAX 801
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int main() {
int n, v[NMAX];
in >> n;
// citim lungimile bețișoarelor
for (int i = 0; i < n; ++i)
in >> v[i];
// sortăm ca să putem aplica regula v[i] + v[j] >= v[k]
sort(v, v + n);
long long cnt = 0;
// alegem primul bețișor al tripletului
for (int i = 0; i < n - 2; ++i)
// alegem al doilea bețișor
for (int j = i + 1; j < n - 1; ++j) {
int s = v[i] + v[j]; // maximul permis pentru v[k]
// căutăm cu binary search cel mai mare k cu v[k] ≤ s
int low = j + 1, high = n - 1, r = j;
while (low <= high) {
int mid = low + (high - low) / 2;
if (v[mid] <= s){
r = mid; // mid poate forma triunghi
low = mid + 1; // căutăm mai la dreapta
}
else
high = mid - 1; // prea mare, mergem la stânga
}
// pentru (i, j) numărul de k valide este (r - j)
cnt += (r - j);
}
out << cnt;
return 0;
}