Mai intai trebuie sa te autentifici.

Cod sursa(job #3324468)

Utilizator mihaiIonitaIonita Mihai Bogdan mihaiIonita 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;
}