Cod sursa(job #430742)

Utilizator dacyanMujdar Dacian dacyan Data 31 martie 2010 12:19:39
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
using namespace std;

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

int BinarySearch(int);
int a[801], n, i, j, v, k;
long long nr;

int main()
{
	fin >> n;
	for ( i = 1; i <= n; i++)
		fin >> a[i];
	fin.close();
	
	sort(a + 1, a + n + 1);

	for ( i = 2; i <= n; i++)
		for ( j = 1; j < i; j++)
			for ( k = n; k > 0; k--)
				if ( a[i] + a[j] <= a[k])
				{
					nr++;
					break;
				}
	fout << nr << '\n';
	fout.close();
	return 0;
}

int BinarySearch(int v)
{
	int st = 1, dr = n, mij;
	while ( st <= dr)
	{
		mij = (st + dr) / 2;
		if ( a[mij] == v) return mij; // returneaza cea mai mica valoare cre  resp conditia
		else
			if ( a[mij] > v) dr = mij - 1;
			if ( a[mij] < v) st = mij + 1;
	}
	return st;
}