Cod sursa(job #2055919)

Utilizator cristinamateiCristina Matei cristinamatei Data 3 noiembrie 2017 22:11:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int v[801];

bool cmp( int x, int y )
{
	return x < y;
}

int cautare( int n, int x )
{
	int i = 0, pas;
	pas = 1 << 16;
	while( pas != 0 )
	{
		if ( i+pas < n && v[ i + pas ] <= x )
			i+=pas;
		pas/=2;
	}
	return i;
}

int main()
{
	int n, i, j, k, nr = 0;
	in >> n;
	for ( i = 0; i < n; i++ )
		in >> v[i];
	sort( v, v + n, cmp);

	for ( i = 0; i < n; i++ )
	{
		for ( j = i+1; j < n; j++ )
		{
			k = cautare(n, v[i] + v[j] );
			if ( k >= j-1 )
			{
				nr+= k - j;
			}
		}
	}
	out << nr;
	return 0;
}