Cod sursa(job #2208046)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 27 mai 2018 23:07:45
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

int binarySearch(int value, int lt, int rt)
{
	int mid, result = -1;
	while (lt <= rt) {
		mid = lt + (rt - lt) / 2;
		if (v[mid] <= value) {
			result = mid;
			lt = mid + 1;
		}
		else rt = mid - 1;
	}
	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 + 1, n);
			if (x != -1) solution += (x - j);
		}

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

    return 0;
}