Mai intai trebuie sa te autentifici.
Cod sursa(job #3324468)
| Utilizator | Data | 22 noiembrie 2025 11:09:46 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 1.2 kb |
#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;
}