Cod sursa(job #196818)

Utilizator marinaMarina Horlescu marina Data 29 iunie 2008 13:24:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
//nrtri - infoarena
#include <stdio.h>
#include <algorithm>
#define INPUT "nrtri.in"
#define OUTPUT "nrtri.out"
#define NMAX 801

int N;

int v[NMAX];

int rez = 0;

using namespace std;

int cautbin(int val)
{
	int i, step;
	for(step = 1; step < N; step <<=1) ;
	for(i = 0; step; step >>= 1)
		if(i + step < N && v[i + step] <= val)
			i += step;
	
	return i;
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d", &N);
	
	int i;
	for(i = 0; i < N; ++i)
		scanf("%d", v+i);
	
	
	sort(v, v + N);
	
	
	int j;
	for(i = 0; i < N-2; ++i)
		for(j = i+1; j < N-1; ++j)
		{
			int poz = cautbin(v[i] + v[j]);
			rez += poz - j;
		}
		
	printf("%d\n", rez);
	return 0;
}