Cod sursa(job #1748930)

Utilizator petrooPetru G petroo Data 27 august 2016 14:41:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <algorithm>
#include <stdio.h>
using namespace std;
int l[801];

int caut_bin(int l1, int l2, int n,int p)
{

    int mid, a = p, b = n, nr = l2 + l1;
    while (a <= b)
    {
        mid = (a + b) / 2;
        if (l[mid] <= nr)
        {
            if (l[mid + 1] > nr || mid == n)
                return mid - p + 1;
            else
                a = mid + 1;

        }
        else
            b = mid - 1;
    }

    return 0;
}

int main(void)
{
    int n, s = 0;
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &l[i]);
    sort(l + 1, l + n + 1);
    for(int i = 1; i < n-1; i++)
        for(int j = i + 1; j < n; j++)
            s += caut_bin(l[i],l[j],n,j + 1);

        printf("%d \n", s);
    return 0;
}