Cod sursa(job #2622554)

Utilizator SahisttulArsene Marinel Sahisttul Data 1 iunie 2020 14:36:13
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("nrtri.in");

ofstream g("nrtri.out");

int v[801], n;

int cautbin(int x)

{

    int p = 1, u = n, poz = -1;

    while(p <= u)

    {

        int m = (p + u) / 2;

        if(x >= v[m])

        {

            poz = m;

            p = m + 1;

        }

        else

            u = m - 1;

    }

    return poz;

}



int main()

{

    int nr = 0;

    f >> n;

    for(int i = 1; i <= n; i++)

        f >> v[i];

    sort(v + 1, v + n + 1);

    for(int i = 1; i < n - 1; i++)

        for(int j = i + 1; j < n; j++)

        {

            int poz = cautbin(v[i] + v[j]);

            if(poz != -1)

                nr += (poz - j);

        }

    g << nr;

    return 0;

}