Cod sursa(job #2172571)

Utilizator 24601Dan Ban 24601 Data 15 martie 2018 16:59:28
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <stdlib.h>

#define SIZE 800

static int v[SIZE+1];

static int qcmp(const void *a, const void *b)
{
    int x = *(const int *) a, y = *(const int *) b;

    return x - y;
}

static int cb(int x, int n)
{
    int mid, pos;

    for (mid = 1; mid < n; mid <<= 1)
        ;

    for (pos = 0; mid; mid >>= 1) {
        if (pos + mid < n && v[pos + mid] <= x) {
            pos += mid;
        }
    }

    return pos;
}

int main(void)
{
    int n, i, j, r;

    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

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

    qsort(v, n, sizeof v[0], qcmp);

    for(r = 0, i = 0; i < n - 1; i++) {
        for(j = i + 1; j < n; j++) {
            r += cb(v[i] + v[j], n) - j;
        }
    }

    printf("%d", r);

    return 0;
}