Cod sursa(job #1155613)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 27 martie 2014 00:51:51
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream ka("nrtri.in");
ofstream ki("nrtri.out");
int n, v[805], s;

int binara(int i, int j)
{
    int inc = j;
    int sf = n;
    int suma = v[i] + v[j];
    while(inc < sf)
    {
        if(inc == sf-1)
        {
            if(suma >= v[sf])
                return sf;
            else
                return inc;
        }
        int mij = (inc+sf)/2;
        if(suma >= v[mij])
            sf = mij;
        else
            inc = mij;
    }
}

int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
        ka >> v[i];
    sort(v+1, v + n + 1);
    for(int i = 1; i <= n-2; i++)
        for(int j = i + 1; j <= n-1; j++)
        {
            s += binara(i, j)- j;
        }
    ki << s;
}