Cod sursa(job #2208043)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 27 mai 2018 22:38:14
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n, x, solution, v[801];

int binarySearch(int value, int lt)
{
	int step, result = -1;
	for (step = 1; step < n; step <<= 1);
	for (int i = lt; step; step >>= 1)
		if (i + step <= n && v[i + step] <= value) {
			i += step;
			result = i;
			break;
		}
	return result;
}

int main()
{
	FILE *in, *out;
	in = freopen("nrtri.in", "r", stdin);
	out = freopen("nrtri.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
	fclose(in);
	sort(v + 1, v + n + 1);

	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++) {
			x = binarySearch(v[i] + v[j], j);
			if (x != -1) solution += (x - j);
		}

	printf("%d", solution);
	fclose(out);

    return 0;
}