Cod sursa(job #447830)

Utilizator giuliutzagiulia petre giuliutza Data 1 mai 2010 12:03:39
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
# include<fstream>
using namespace std;

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

int main()
{
	int v[801],n,i,x,j,pmin,aux,cnt=0,m,st,dr;
	in>>n;
	for(i=1;i<=n;++i)
		in>>v[i];
	for(i=1;i<=n-1;++i)
	{
		pmin=i;
		for(j=i+1;j<=n;++j)
		{
			if(v[j]<v[pmin])
				pmin=j;
		}
		if(pmin!=i)
		{
			aux=v[i];
			v[i]=v[pmin];
			v[pmin]=aux;
		}
	}
	for(i=1;i<=n;++i)
	{
		for(j=i+1;j<=n;++j)
		{
			x=v[i]+v[j];
			//caut cel mai mare indice k, cu v[k]<=x
			st=1;
			dr=n;
			while(st<dr)
			{
				m=(st+dr+1)/2;
				if(x>=v[m])
					st=m;
				else
					dr=m-1;
			}
			cnt+=st-j;
		}
	}
	out<<cnt;
	return 0;
}