Cod sursa(job #629018)

Utilizator irene_mFMI Irina Iancu irene_m Data 2 noiembrie 2011 16:21:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#define MaxN 805

using namespace std;

int N, v[ MaxN ], nrSol;

void read()
{
    int i;
    freopen( "nrtri.in", "r", stdin);
    cin >> N;
    for( i = 1; i <=N; ++i)
        cin >> v[ i ];
    fclose(stdin);
}

int search(int val, int li, int lf)
{
    int m  = li + (lf - li)/2 ;
    while( li < lf )
    {
        if( v[ m ] > val )
            lf = m - 1;
        else
            li = m + 1;
        m = li + (lf - li)/2;
    }

    if( v[ m ] <= val )
        return m;
    return m - 1;
}

void solve()
{
    int i, j;

    for( i = 1; i <N; ++i )
        for( j = i+1 ; j <N ; ++j )
           nrSol += ( search( v[ i ] + v[ j ], j + 1, N ) - j);
}

void write()
{
    freopen("nrtri.out","w",stdout);
    cout << nrSol << "\n";
    fclose(stdout);
}

int main()
{
    read();
    sort(v+1,v+N+1);
    solve();
    write();
    return 0;
}