Cod sursa(job #2300118)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 10 decembrie 2018 21:34:11
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n,a[803];

void Citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
}
int CautBin(int x)
{
    int st,dr,mij,poz;
    poz = 0;
    st = 1;
    dr = n;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(x >= a[mij])
        {
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int cautbin(int x)
{
    int p=1,u=n,poz=0;
    while(p<=u)
    {
        int mij=(p+u)/2;
        if(x>=a[mij])
        {
            poz=mij;
            p=mij+1;
        }
        else u=mij-1;

    }
    return poz;
}


void Rezolvare()
{
    int i,j,sol;
    sol = 0;
    sort(a+1,a+n+1);
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
            sol += (CautBin(a[i] + a[j]) - j);
    fout<<sol<<"\n";
}

int main()
{
    Citire();
    Rezolvare();

    fin.close();
    fout.close();
    return 0;
}