Cod sursa(job #333177)

Utilizator andreea_beicaBeica Andreea andreea_beica Data 21 iulie 2009 17:23:49
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>

using namespace std;

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

int n,v[801],nr[30001],n1=0;
int cautbin(int x)
{
	int st=1,dr=n,mij;
	while(st!=dr)
	{
		mij=(st+dr+1)/2;
		if(v[mij]<=x)
			st=mij;
		else dr=mij-1;
	}
	if(v[st]>x)
		return st-1;
	return st;
}

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