Cod sursa(job #801419)

Utilizator bambambamBam Bam bambambam Data 24 octombrie 2012 11:23:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<cstdio>
#include<cstdlib>
int a[1000],n;
int comp(const void *p, const void *q)
{
    int d = *(int*)p, b = *(int*)q;
    if(d<b) return -1;
    if(d>b) return 1;
	return 0;
}
int cautare (int x)
{
		int z=0, c=n-1,m;
		while(z<c)
		{
			m=(z+c+1)/2;
			if(x>=a[m])
				z=m;
			else
				c=m-1;
		}
		if(x>=a[z])
			return z;
		return 0;
}
int main()
{
		int w=0,i,j,g;
		freopen("nrtri.in","r",stdin);
		freopen("nrtri.out","w",stdout);
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		qsort(a,n,sizeof(a[0]),comp);
		for(i=0;i<n;i++)
				for(j=i+1;j<n;j++)
				{
					g=cautare(a[i]+a[j]);
					if(g>j)
						w=w+(g-j);
				}
		printf("%d",w);
}