Cod sursa(job #629097)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 2 noiembrie 2011 17:18:48
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
# include<stdio.h>
# include <algorithm>
using namespace std;
int n,i,j,p,q,alfa,beta,nr,a[1000],x,y,l,r,m;

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d\n",&n);
	for (i=1; i<=n; i++)
		scanf("%d ",&a[i]);
	for (i=1; i<n; i++)
		for (j=i+1; j<n; j++)
		{
			p=a[i]; q=a[j];y=p+q;
			l=j+1; r=n;
			m=(l+r)/2;
			while (l<=r)
			{
				if (a[m]<y) l=m+1;
				else
					r=m-1;
			}
			beta=m;
			if (a[beta]<=y) nr=nr+beta-j;
			else
				nr=nr+beta-1-j;
		}
	printf("%d\n",nr);
	return 0;
}