Cod sursa(job #1122166)

Utilizator gedicaAlpaca Gedit gedica Data 25 februarie 2014 16:45:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<cstdio>
#include<algorithm>

using namespace std;



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

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int n, nrtri;
    scanf("%d", &n );
    for ( int i= 0; i<n; ++i ) {
        scanf("%d", &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= j;
            for ( pas = n2; pas>0; pas /= 2 ) {
                if ( sol+pas<n && v[sol+pas]<=s )
                    sol+= pas;
            }
            nrtri+= sol-j;
        }
    }
    printf("%d\n", nrtri);

    return 0;
}