Cod sursa(job #2203064)

Utilizator mihailrazMihail Turcan mihailraz Data 10 mai 2018 20:15:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
#define NMAX 800

using namespace std;
ifstream fi("nrtri.in");
ofstream fo("nrtri.out");
int n, rez, x;
int X[NMAX+5];

void citire(void)
{
    fi>>n;
    for(int i=1; i<=n; i++)
        fi>>X[i];
}

int cautBin(int val, int st, int dr)
{
    int mid, result=-1;
    while(st<=dr)
    {
        mid=st+(dr-st)/2;
        if(X[mid]<=val)
        {
            result=mid;
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    return result;
}

int main()
{
    citire();
    sort(X+1, X+n+1);
    for(int i=1; i<=n-1; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            x=cautBin(X[i]+X[j], j+1, n);
            if(x!=-1)
                rez+=(x-j);
        }
    }
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}