Cod sursa(job #624901)

Utilizator sebii_cSebastian Claici sebii_c Data 23 octombrie 2011 11:57:14
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 805

int A[NMAX];
int N;

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    int i, j, k, step, sum, lg, nr=0;
    scanf("%d", &N);
    for (i=1; i<=N; ++i)
        scanf("%d", &A[i]);
    qsort(A, N+1, sizeof(int), compare);
    for (step=1; step<=N; step<<=1);
    for (i=1; i<=N-2; ++i)
        for (j=i+1; j<=N-1; ++j) {
	sum = A[i] + A[j];
	for (k=j, lg=step; lg; lg>>=1) 
	    if (k+lg<=N && (A[k+lg]<=sum))
	        k+=lg;
	if (A[k] > sum)
	    continue;
	nr+=(k-j);
        }
    printf("%d\n", nr);
    return 0;
}