Cod sursa(job #629045)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 2 noiembrie 2011 16:40:09
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda gc_practice Marime 0.59 kb
#include <stdio.h>
#include <algorithm>

#define max_n 801

using namespace std;

int i,n,a[max_n];
int st,dr,m,nr,s,j;

int cb() {
	st=j+1;
	dr=n;
	m=(st+dr)/2;
	while (st<dr) {
		m=(st+dr)/2;
		if (a[m]>s) dr=m-1;
		else st=m+1;
	}
	if (a[m]<=s) return m;
    else return m-1;	
}

int main () {
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	nr=0;
	for (i=1; i<n; i++)
		for (j=i+1; j<=n; j++) {
			s=a[i]+a[j];
			nr+=cb()-j;
		}
	printf("%d\n",nr);
	return 0;
}