Cod sursa(job #3185449)

Utilizator andreidumitrache1709Dumitrache Andrei Bogdan andreidumitrache1709 Data 18 decembrie 2023 20:53:50
Problema Numarare triunghiuri Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000
#define MAXBAT 30000
short bete[MAXN + 1];
short f[MAXBAT + 1];
int main() {
    FILE *fin , *fout;
    int n , i , bat , triunghiuri , j , z , st , dr , mij , cop;
    short a , b , c;
    fin = fopen ( "nrtri.in" , "r" );
    fscanf ( fin , "%d" , &n );
    for ( i = 0 ; i < n ; i++ ) {
        fscanf ( fin , "%d" , &bat );
        f[bat]++;
    }
    fclose ( fin );
    n = 0;
    for ( i = 1 ; i <= MAXBAT ; i++ )
        while ( f[i] > 0 ) {
            bete[++n] = i;
            f[i]--;
        }
    triunghiuri = 0;
    for ( i = 1 ; i <= n ; i++ )
        for ( j = i + 1 ; j <= n ; j++ ) {
            st = j;
            dr = n;
            cop = j;
            // imi cer scuze pentru aceasta cautare binara
            while ( st <= dr ) {
                mij = ( st + dr ) / 2;
                if ( bete[mij] <= bete[i] + bete[j] ) {
                    st = mij + 1;
                    cop = mij;
                } else
                    mij = dr - 1;
            }
            triunghiuri += st - cop;
        }
    fout = fopen ( "nrtri.out" , "w" );
    fprintf ( fout , "%d\n" , triunghiuri );
    fclose ( fout );
    return 0;
}