Cod sursa(job #771015)

Utilizator badmanDragan Dan badman Data 24 iulie 2012 15:58:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <algorithm>
#define N 800

using namespace std;

int a[N];

int bs(int n, int x) {
    int i, step;
    for(step = 1; step < n; step <<= 1);
    for(i = 0; step; step >>= 1)
        if (i + step < n && a[i + step] <= x)
           i += step;
    return i;
}



int main() {
    freopen ("nrtri.in", "r", stdin);
    freopen ("nrtri.out", "w", stdout);
	int n, x, k = 0;

	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	sort(a, a + n);

	for(int i = 0; i < n - 2; i++) {
		for(int j = i + 1; j < n - 1; j++) {
			x = bs(n, a[i] + a[j]);
			if(a[x] <= (a[i] + a[j]))
                if(x - j > 0)
                    k += x - j;
			else
                if(x - j - 1 > 0)
				k += x - j - 1;
		}
	}
    printf("%d", k);

	return 0;
}