Cod sursa(job #214532)

Utilizator Mishu91Andrei Misarca Mishu91 Data 14 octombrie 2008 22:57:06
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_N 805

int V[MAX_N], S, Rez;
int N;

int b_search(int li, int lf)
{
    while(li <= lf)
    {
        int m = li + ((lf - li) >> 1);

        if(V[m] <= S && V[m + 1] > S)
            return m;

        if(V[m] < S)
            lf = m - 1;
        else
            li = m + 1;
    }
    return N + 1;

}

void citire()
{
    scanf("%d\n",&N);

    for(int i = 1; i <= N; ++i)
        scanf("%d",V+i);
}

void solve()
{
    sort(V+1, V+N+1);

    for(int i = 1; i < N; ++i)
        for(int j = i + 1; j <= N; ++j)
        {
            S = V[i] + V[j];

            int nr = b_search(j + 1, N);
            Rez += (N - nr + 1);
        }
    printf("%d\n",Rez);
}

int main()
{
    freopen("nrtri.in","rt",stdin);
    freopen("nrtri.out","wt",stdout);
    citire();
    solve();
}