Cod sursa(job #2326086)

Utilizator marcogoldPop Mihali Marco Silviu marcogold Data 23 ianuarie 2019 12:30:53
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda simulare_preoli Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ofstream fo("nrtri.out");
ifstream fi("nrtri.in");


int n,trig[900];
long long sol;
int cautbin(int cautat)
{
    int poz=0;

    for(int i=19;i>=0;i--)
    {
        if(poz+(1<<i) && trig[poz+(1<<i)]<cautat)
        {
            poz+(1<<i);
        }
    }

    return poz;
}

int main()
{
   fi>>n;
   for(int i=1;i<=n;i++)
    fi>>trig[i];

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

    for(int i=1;i<n-1;i++)
        for(int j=i+1;j<n;j++)
        {
            int suma=trig[i]+trig[j];
            int pozitie=cautbin(suma);


            sol+=n-pozitie;
        }



   fo<<sol/6;

   fo.close();
   fi.close();
    return 0;
}