Cod sursa(job #1195421)

Utilizator cristinamateiCristina Matei cristinamatei Data 7 iunie 2014 10:24:44
Problema Numarare triunghiuri Scor 0
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;
    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++ )
        {
            if ( cautare(a[i] + a[j] ) == 0 || cautare( a[i] + a[j] ) == j )
                continue;
            nr++;
        }
    }
    out << nr;
    return 0;
}