Cod sursa(job #1493774)

Utilizator czlateaZlatea Cezar czlatea Data 29 septembrie 2015 21:21:15
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[805] ;
int f ( int a , int b , int n )
{
    int i , sol = 0 , ok = 1 ;
    int st = b + 1 , dr = n ;
    int med , last = 0 ;
    while ( st <= dr )
    {
        med = ( st + dr ) / 2 ;
        if ( v[med] > v[a] + v[b] )
            dr = med - 1 ;
        if ( v[med] < v[a] + v[b] )
        {
            st = med + 1 ;
            last =  med ;
        }
        if ( v[med] == v[a] + v[b] )
            {
                ok = 0 ;
                last = med ;
                sol = last - b ;
                return sol ;
            }
    }
    if ( ok == 1 && last > b )
        return last - b ;
    return 0 ;
}
int main()
{
    freopen ( "nrtri.in" , "r" , stdin ) ;
    freopen ( "nrtri.out" , "w" , stdout ) ;
    int n , i , j , sol , s = 0 ;
    scanf ( "%d" , &n ) ;
    for ( i = 1 ; i <= n ; i ++ )
        scanf ( "%d" , &v[i] ) ;
        sort ( v + 1 , v + n + 1 ) ;
    for ( i = 1 ; i <= n ; i ++ )
        for ( j = i + 1 ; j < n ; j ++ )
    {
        sol = f ( i , j , n ) ;
        s += sol ;
    }
    printf ( "%d\n" , s ) ;
    return 0;
}