Cod sursa(job #1195425)

Utilizator cristinamateiCristina Matei cristinamatei Data 7 iunie 2014 11:00:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <algorithm>

using namespace std;

int a[801], n;
bool cmp( int x, int y )
{
    return x < y;
}

int cautare( int x )
{
    int i = 0, pas;
    pas = 1 << 16;
    while( pas != 0 )
    {
        if ( i + pas <= n && a[i + pas] <= x )
            i+=pas;
        pas/=2;
    }
    return i;
}

int main()
{
    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    int i, j, nr = 0, k;
    in >> n;
    for ( i = 1; i <= n; i++ )
        in >> a[i];
    sort ( a + 1, a + 1 + n, cmp );
    for ( i = 1; i < n; i++ )
    {
        for ( j = i + 1; j <= n; j++ )
        {
            k = cautare(a[i] + a[j] );
            if(k >= j - 1){
                nr += k - j ;
            }
        }
    }
    out << nr;
    return 0;
}