Cod sursa(job #1521790)

Utilizator danielmaxim95FMI Maxim Daniel danielmaxim95 Data 10 noiembrie 2015 20:42:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int v[800], n;
long long int suma = 0;

void citeste()
{
	FILE *f = fopen("nrtri.in", "r");
	fscanf(f, "%i", &n);
	for (int i = 0; i < n; i++)
		fscanf(f, "%i", &v[i]);
	fclose(f);
}

int cautbin(int s, int d, int val)
{
	int m;
	while (s<d)
	{
		m = (s + d) / 2 + 1;
		if (v[m] <= val)
			s = m;
		else
			d = m - 1;
	}

		return s;
}

void cauta(int i, int j)
{
	int d = cautbin(j, n - 1, v[j] + v[i]);
	suma += d - j;
}

void rezolva()
{
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			cauta(i, j);
}

void afiseaza()
{
	FILE *f = fopen("nrtri.out", "w");
	fprintf(f, "%lli", suma);
	fclose(f);
}

int main()
{
	citeste();
	sort(v, v + n);
	rezolva();
	afiseaza();
	return 0;
}