Cod sursa(job #63712)

Utilizator scapryConstantin Berzan scapry Data 30 mai 2007 11:15:55
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#include <assert.h>
#include <algorithm>
using namespace std;

enum { maxn = 801, maxv = 30001 };

int n;
int len[maxn];
int first[maxv]; //first of magnitude >= i in sorted array len[]
int ans;

void precalc()
{
	int i, pos;

	std::sort(len, len + n);

	pos = 0;
	for(i = 0; i < maxv; i++)
	{
		while(len[pos] < i && pos < n)
			pos++;

		first[i] = pos;
	}
}

void calc()
{
	int i, j, sub;

	for(i = 0; i < n; i++)
		for(j = i + 1; j < n; j++)
		{
			assert(len[j] >= len[i]);

			if(len[i] >= len[j] - len[i]) //must subtract both
				sub = 2;
			else //must only subtract j
				sub = 1;

			ans += first[ len[i] + len[j] + 1 ] - first[ len[j] - len[i] ] - sub;
		}

	assert(ans >= 0);
	assert((ans % 3) == 0);
	ans /= 3;
}

int main()
{
	int i;
	FILE *f = fopen("nrtri.in", "r");
	if(!f) return 1;

	fscanf(f, "%d", &n);
	for(i = 0; i < n; i++)
		fscanf(f, "%d", &len[i]);

	fclose(f);
	f = fopen("nrtri.out", "w");
	if(!f) return 1;

	precalc();
	calc();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}