Cod sursa(job #583747)

Utilizator truenighttruenight truenight Data 22 aprilie 2011 14:14:31
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>

#define IN "nrtri.in"
#define OUT "nrtri.out"
#define N 801

static int v[N];

static void bubblesort(int);
static int cautbin(int, int, int);

int main(void) {

    int n, i, j;
    long nrtri = 0;

    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);

    (void) scanf("%d", &n);

    for(i = 1; i <= n; ++i) scanf("%d", &v[i]);

    bubblesort(n);

    for(i = 1; i < n - 1; ++i) for(j = i + 1; j < n; ++j)
        nrtri += cautbin(1, n, v[i] + v[j]) - j;

    printf("%ld\n", nrtri);

    return 0;
}

void bubblesort(int n) {

    int sortat, i, aux;

    do {

        sortat = 1;

        for(i = 1; i < n; ++i)
            if(v[i] > v[i + 1]) aux = v[i], v[i] = v[i + 1], v[i + 1] = aux,
                sortat = 0;
    } while(!sortat);
}

int cautbin(int lo, int hi, int n) {

    int mid;

    do {
        
        mid = lo + (hi - lo) / 2;

        if(v[mid] < n) lo = mid + 1;
        else hi = mid - 1;
    } while(lo <= hi && v[mid] != n);

    if(v[mid] > n) -- mid;
    if(v[mid] == n) while(v[mid + 1] == n) ++mid;

    return mid;
}