Cod sursa(job #1984098)

Utilizator deleted_2dbcc643895c1cb0DELETED deleted_2dbcc643895c1cb0 Data 23 mai 2017 18:04:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[100000];
int cautbin (int x)
{
    int ls = 1,ld=n;
    int m, pozitie = 0;
    while (ls <=ld)
    {
        m = ls + (ld-ls)/2;
        if (v[m] <=x)
        {
            ls=m+1;
            pozitie = m;
        }
        else ld = m-1;
    }
    return pozitie;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++) f >> v[i];
    sort (v+1,v+n+1);
    int ct=0;
    for  (int i=1; i<=n; i++)
        for (int j=i+1; j<=n-1; j++)
            ct+=(cautbin(v[i]+v[j])-j);
    g << ct;
    return 0;
}