Cod sursa(job #2347052)

Utilizator daria_stoianStoian Daria Alexandra daria_stoian Data 18 februarie 2019 12:50:06
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define L 9

using namespace std;
int v[801], n;

int caut( int x ){
    int r = 0, pas = 1 << L;
    while ( pas != 0 ){
        if ( r + pas <= n && v[r + pas] <= x ){
            r += pas;
        }
        pas /= 2;
    }
    return r;
}

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