Cod sursa(job #788706)

Utilizator vld7Campeanu Vlad vld7 Data 15 septembrie 2012 17:22:48
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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--;
	return mid;
}

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

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