Cod sursa(job #501167)

Utilizator bogdanvilceleanuBogdan Vilceleanu bogdanvilceleanu Data 14 noiembrie 2010 14:28:56
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<algorithm>
using namespace std;
long n,x[3005];
long bsdr(long p)
{
	long st=1,dr=n,last=1,med;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(x[med]<=p)
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
long bsst(long p)
{
    long st,dr,med,last=1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        if(p>x[med])
                st=med+1;
        else
        if(p<=x[med])
            {
                dr=med-1;
                last=med;
            }
    }
    return last;
}
long bs(long val)
{
    int st,dr,med;
    st=1;
    dr=n;
    while(st<=dr)
    {
        med=(st+dr)/2;
        med=st+((dr-st)>>1);
        if(val==x[med])
            return 1;
        else
            if(val>x[med])
                st=med+1;
        else
            dr=med-1;
    }
    return 0;
}
int main()
{
	long i,j,limst,limdr;
	long t;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld",&x[i]);
	sort(x+1,x+n+1);
	t=0;
	limst=0;
	limdr=0;
	for(i=1;i<=n-2;i++)
	{
 		for(j=i+1;j<=n-1;j++)
		{
			limst=bsst(x[i]+x[j]);
			limdr=bsdr(x[i]+x[j]);
            t=t+(limdr-limst)+1+bs(x[i]+x[j]);
		}
	}
	printf("%ld\n",t);
	return 0;
}