Cod sursa(job #629975)

Utilizator George25Raduta George Cristian George25 Data 4 noiembrie 2011 12:55:07
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int i,n,poz,sum,j,k,nr,a[801];

inline void cb(int x,int xx){
	int st,dr,mij;
	st=xx;
	dr=n;
	mij=(st+dr)/2;
	while (st<=dr){
		if (a[mij]<x)
		{
			poz=mij;
			st=mij+1;
			mij=(st+dr)/2;
		}
		else
		if (a[mij]>x)
		{
			dr=mij-1;
			mij=(st+dr)/2;
		}
		else
		if (a[mij]==x)
		{
			poz=mij;
			break;
		}
	}
}

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);
	for (i=1; i<=n-2; ++i)
	{
		for (j=i+1; j<=n-1; ++j)
		{
			sum=a[i]+a[j];
			poz=j;
			cb(sum,j+1);
			nr+=poz-j;
		}	
	}	
	printf("%d",nr);
	return(0);
}