Cod sursa(job #719773)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 22 martie 2012 01:20:40
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#include<algorithm>
#include<cmath>

#define INfile "nrtri.in"
#define OUTfile "nrtri.out"

#define NMAX 900
#define VMAX 30009

using namespace std ;

ifstream F ( INfile ) ;
ofstream G ( OUTfile ) ;

int N , nrt ;
int nr [ NMAX] , V [ NMAX ] ;

void read () ;
void solve () ;
void write () ;

int main ()
{
    read () ;

    solve () ;

    write () ;

    F.close () ;
    G.close () ;
    return 0 ;
}

void read ()
{
    int i ;

    F >> N ;

    for ( i = 1 ; i <= N ; ++ i )
        F >> V [ i ] ;

    sort ( V + 1 , V + 1 + N ) ;
}

void solve ()
{
    int i , j , s , sq , k ;
    sq = sqrt ( N ) ;
    for ( i = 1 ; i < N - 1 ; ++ i )
        for ( j = i + 1 ; j < N ; ++ j )
        {
            s = V [ i ] + V [ j ] ;
            k = j + 1;
            while ( V [ k ] <= s && k <= N )
                k += sq;
            while ( k > N || V [ k ] > s )
                -- k ;
            nrt += k - j ;
        }

}

void write ()
{
    G << nrt << '\n' ;
}