Cod sursa(job #1493807)

Utilizator dnprxDan Pracsiu dnprx Data 29 septembrie 2015 21:56:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

int a[1001], n;

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

int main()
{
    int i, j, cnt, p;
    ifstream fin("nrtri.in");
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();

    sort(a + 1, a + n + 1);
    cnt = 0;
    for (i = 1; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
        {
            p = CautBin(j + 1, n, a[i]+a[j]);
            if (p > 0) cnt += (p - j);
        }

    ofstream fout("nrtri.out");
    fout << cnt << "\n";
    fout.close();

    return 0;
}