Cod sursa(job #3130401)

Utilizator Roxana_3Asavei Roxana Roxana_3 Data 17 mai 2023 18:34:17
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>
#define N 800
using namespace std;

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

int n, a[N + 5];
int ct;

void Citire()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
}

int CB(int st, int dr, int x)
{
    int possible = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(a[mij] > x) possible = mij, dr = mij - 1;
        else st = mij + 1;
    }

    return possible;
}

void Rezolvare()
{
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
    {
        /// cautam prima poz pt care a[i] >= x
        int p;
        p = CB(1, n, a[i] + a[j]);
        if(p != -1) ct += (n - p + 1);
    }

    fout << ct;

}

int main()
{
    Citire();
    sort(a + 1, a + n + 1);
    Rezolvare();

    return 0;
}