Cod sursa(job #73161)

Utilizator c_sebiSebastian Crisan c_sebi Data 17 iulie 2007 09:42:51
Problema Numarare triunghiuri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>

int v[800], nr[90001], n;

void read() {
	int i;
	FILE *f = fopen("nrtri.in", "r");
	fscanf(f, "%d", &n);
	for (i = 0; i < n; ++i) {
		fscanf(f, "%d", &v[i]);
		nr[v[i]]++;
	}
	for(i = 2; i <= 9000; ++i)
		nr[i] = nr[i-1] + nr[i];
	fclose(f);
}


int main() {
	int i, j, dif, a, b;
	long long REZ = 0;
	read();
	for (i = 0; i < n-1; ++i)
		for(j = i+1; j < n; ++j) {
			a = v[i]; b = v[j];
			a>=b?dif=a-b:dif=b-a;
			if (dif > 0)
				REZ += (nr[a+b] - nr[dif-1]);
			else REZ += nr[a+b];
			if (a >= dif) REZ--;
			if (b >= dif) REZ--;

		}
	REZ /= 3;
	FILE *g = fopen("nrtri.out", "w");
	fprintf(g, "%lld\n", REZ);
	fclose(g);
	return 0;
}