Cod sursa(job #1057948)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 14 decembrie 2013 21:13:04
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin ( "nrtri.in" );
ofstream fout ( "nrtri.out" );

const int nmax = 800;
int v[nmax];

int main()
{
    int n, nrtri;
    fin>>n;
    for ( int i = 0; i<n; ++i ) {
        fin>>v[i];
    }
    sort( v, v+n );
    nrtri = 0;
    for ( int i = 0; i<n-2; ++i ) {
        for ( int j = i+1; j<n-1; ++j ) {
            int n2, s;
            s = v[i] + v[j];
            for ( n2 = 1; 2*n2<=s; n2 *= 2 ){
            }
            int pas, sol;
            sol = n;
            for ( pas = n2; pas>0; pas /= 2 ) {
                if ( sol-pas>j && v[sol-pas]<=s )
                    sol -= pas;
            }
            if ( sol==n )
                sol = j;
            nrtri += sol-j;
        }
    }
    fout<<nrtri<<'\n';
    fin.close();
    fout.close();
    return 0;
}