Cod sursa(job #2169438)

Utilizator andonis1616And Cuz andonis1616 Data 14 martie 2018 15:30:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("nrtri.in");
ofstream out ("nrtri.out");

int n,v[805];
int t;

int cautbin(int x,int y,int val)
{
    int mij;
    while(x<y)
    {
        mij=(x+y)/2;
        if(v[mij]+v[mij+1]==val)
            return mij;
        else
            if(v[mij]<val)
                x=mij+1;
            else
                y=mij-1;
    }
    if(v[mij]+v[mij+1]<val)
        return -1;
    else
        return mij;
}

int main()
{
    int i,j;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    sort(v+1,v+1+n);
    for(i=3;i<=n;i++)
    {
        j=cautbin(1,i-1,v[i]);
        if(j!=-1)
            t=t+(i-j-1)*(i-j)/2;
    }
    out<<t;
    return 0;
}