Cod sursa(job #333184)

Utilizator bogfunFMI Chicos Bogdan bogfun Data 21 iulie 2009 17:33:18
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int nr[30001],n=0,v[801];

int cbin(int x, int poz) 
{
	int st=poz,dr=n,mijl;
	while(st!=dr)
	{
		mijl=(st+dr+1)/2;
		if(x>=v[mijl])
			st=mijl;
		else
			dr=mijl-1;
	}
	if(v[st]<=x)
		return st;
	return st-1;
}

int main()
{
	int s=0,i,j,x;
	in>>n;
	for(i=1;i<=n;++i)
	{
		in>>x;
		++nr[x];
	}
	n=0;
	for(i=1;i<=30000;++i)
		while(nr[i]--) v[++n]=i;
	for(i=1;i<n-1;++i)
		for(j=i+1;j<n;++j)
			s+=cbin(v[i]+v[j],j+1)-j;
	out<<s;
	
	in.close();
	out.close();
	return 0;
}