Cod sursa(job #445320)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 aprilie 2010 15:13:08
Problema Numarare triunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "nrtri.in"
#define file_out "nrtri.out"

int n,v[1000];

void citire()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		 scanf("%d", &v[i]);
	sort(v+1,v+n+1);
}


void solve()
{
	int i,j,k,rez=0;
	
	//O(N^3)-optimizat
	
	for (i=1;i<n-1;++i)
		 for (j=i+1;j<n;++j)
		 {
			 int ok=0;
			  for (k=j+1;k<=n && !ok;++k) 
			       if (v[i]+v[j]>=v[k])
					   rez++;
				   else
					   ok=1;
		 }
		 
	printf("%d", rez);
}


int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}