Cod sursa(job #3131528)

Utilizator patrick_burasanPatrick Burasan patrick_burasan Data 20 mai 2023 14:31:04
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int CautBin(int a[], int n, int x)
{
    if (x < a[0]) return 0;
    if (x > a[n - 1]) return n - 1;

    int st, dr, mid, p;
    st = 0;
    dr = n - 1;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (x >= a[mid])
        {
            p = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return p;
}

int v[800];

int main()
{
    int N, i, cnt = 0;
    in >> N;
    for (i = 0; i < N; ++i)
        in >> v[i];
    in.close();

    sort(v, v + N);

    for (i = 0; i < N - 2; ++i)
    {
        int L = v[i] + v[i + 1];
        int Lmax = CautBin(v, N, L);
        cnt += Lmax - i - 1;
    }

    out << cnt << '\n';
    out.close();
    return 0;
}