Cod sursa(job #241532)

Utilizator Cezar_16Cezar Ghimbas Cezar_16 Data 10 ianuarie 2009 12:50:09
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<fstream>
using namespace std;
int main()
{
	ifstream in("nrtri.in");
	ofstream out("nrtri.out");
	int i,pmin,aux, j, k,n,s=0, a[805];
	in>>n;
	for(i=1; i<=n; ++i)
		in>>a[i];
	for(i=1; i<n; ++i)
	{
		pmin=i;
		for(j=i+1; j<=n; ++j)
			if(a[j]<a[pmin])
				pmin=j;
		if(i!=pmin)
		{
			aux=a[i]; 
			a[i]=a[pmin];
			a[pmin]=aux;
		}
	}
	for(i=1; i<n-1; ++i)
	{
		for(k=i+2; k<=n && a[k]<=a[i] + a[i+1]; ++k);
		for(j=i+1; j<n; ++j)
		{
			while(k<=n && a[k]<=a[i] + a[j]) ++k;
			s+=k-j-1;
		}
	}
	out<<s;
	in.close();
	out.close();
}