Cod sursa(job #788714)

Utilizator vld7Campeanu Vlad vld7 Data 15 septembrie 2012 17:42:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>

#define maxN 805

using namespace std;

FILE *f = fopen ("nrtri.in","r");
FILE *g = fopen ("nrtri.out","w");

int n, a[maxN], SOL;

void read()
{
	fscanf (f, "%d", &n);
	for (int i = 1; i <= n; i++)
		fscanf (f, "%d", &a[i]);
	sort (a + 1, a + n + 1);
}

int bsearch(int i, int val)
{
	int lo = i, hi = n, mid;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (a[mid] > val)
			hi = mid - 1;
		else
			lo = mid + 1;
	}
	if (a[mid] > val)
		mid--;
	if (val >= a[mid])
		return mid;
	return -1;
}

void solve()
{
	for (int i = 1; i <= n - 2; i++)
		for (int j = i + 1; j <= n - 1; j++) {
			int sum = a[i] + a[j];
			int poz = bsearch(j + 1, sum);
			if (poz != -1)
				SOL += poz - (j + 1) + 1;
	}
	
	fprintf (g, "%d\n", SOL);
}

int main()
{
	read();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}