Cod sursa(job #3324435)

Utilizator adidavidDumitrascu Adrian David adidavid Data 22 noiembrie 2025 10:52:38
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
// 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;
}