Cod sursa(job #1792219)

Utilizator crazylamaRiclea Andrei crazylama Data 30 octombrie 2016 11:04:45
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n;
vector<int> v;

int CautareBinara(int st, int dr, int x)
{
    if (st <= dr)
    {
        int mij = st + (dr - st) / 2;
        if (v[mij] == x)
            return mij;
        else if (v[mij] > x)
            return CautareBinara(st, mij - 1, x);
        else
            return CautareBinara(mij + 1, dr, x);
    }
    return dr;
}

int main()
{
    int sum = 0;
    f >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i)
        f >> v[i];
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
        sum += n - CautareBinara(j, n - 1, v[i] + v[j]) - 1;
    g << sum;
    return 0;
}