Cod sursa(job #3131532)

Utilizator patrick_burasanPatrick Burasan patrick_burasan Data 20 mai 2023 14:43:47
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 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, j, 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)
    {
        for (j = i + 1; j < N - 1; ++j)
        {
            int L = v[i] + v[j];
            int ind = CautBin(v, N, L);
            cnt += ind - j;
        }
    }

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