Cod sursa(job #1799430)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 6 noiembrie 2016 12:45:57
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define L 10

using namespace std;

int v[801];

int cautareBinara( int n, int nr, int st ) {
    int r = st, pas;
    pas = 1 << L;
    while ( pas != 0 ) {
        if ( r + pas <= n && v[r+pas] <= nr )
            r += pas;
        pas /= 2;
    }
    if ( r > n || v[r] > nr )
        return 0;
    return r - st + 1;
}

int main() {
    FILE *fin, *fout;
    int n, i, j, nrtri;
    fin = fopen( "nrtri.in", "r" );
    fout = fopen( "nrtri.out", "w" );
    fscanf( fin, "%d", &n );
    for ( i = 1; i <= n; i++ )
        fscanf( fin, "%d", &v[i] );
    sort( v + 1, v + n + 1 );
    nrtri = 0;
    for ( i = 1; i <= n; i++ )
        for ( j = i + 1; j <= n; j++ )
            nrtri += cautareBinara( n, v[i] + v[j], j + 1 );
    fprintf( fout, "%d", nrtri );
    fclose( fin );
    fclose( fout );
    return 0;
}