Cod sursa(job #58324)

Utilizator risenshineAkil Nasser risenshine Data 5 mai 2007 12:24:51
Problema Numarare triunghiuri Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#define NMAX 801
#define LMAX 30001

int N, bat[NMAX], lbat[LMAX], s, last;
int ntri;

void search(int p, int q) {
	if (p <= q) {
		int m = (p+q)/2;
		if (bat[m] <= s) {
			if (last < m)
				last = m; //printf("%d %d\n", m, last);
			search(m+1, q);
		}
		search(p, m-1);
	}
}
int main() {
	FILE *fi = freopen("nrtri.in", "r", stdin);
	FILE *fo = freopen("nrtri.out", "w", stdout);
	int i, j, a;
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		scanf("%d", &a);
		++lbat[a];
	}
	for (i = 1, N = 0; i < LMAX; ++i) {
		for (j = 0; j < lbat[i]; ++j)
			bat[N++] = i;
	}
	for (i = 0; i < N-2; ++i)
		for (j = i+1; j < N-1; ++j) {
			s = bat[i] + bat[j];
			last = -1;
			search(j+1, N-1);
			if (last != -1)
				ntri += last - j;
		}
	printf("%d\n", ntri);
	return 0;
}