Cod sursa(job #2496099)

Utilizator sebimihMihalache Sebastian sebimih Data 20 noiembrie 2019 11:13:42
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
int const N = 1000;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int bsUltimul(int n, int LungimeBat[], int SumaLaturilor)
{
	int sol = 0;
	int pas = 1 << 10;

	while (pas > 0)
	{
		if (sol + pas < n && LungimeBat[sol + pas] <= SumaLaturilor)
		{
			sol += pas;
		}
		pas /= 2;
	}

	return sol;
}

int bsPrimul(int n, int LungimeBat[], int SumaLaturilor)
{
	int sol = bsUltimul(n, LungimeBat, SumaLaturilor - 1);
	if (sol < SumaLaturilor)
	{
		sol++;
	}

	return sol;
}

int main()
{
	/** Pentru a forma un triunghi:
		* a + b >= c
		* b + c >= a
		* a + c >= b

		[abs(i - j); i + j]
		cautam binar numerele din interval
	*/

	int n;
	fin >> n;

	int contor = 0;
	int LungimeBat[N];

	for (int i = 0; i < n; i++)
	{
		fin >> LungimeBat[i];
	}

	sort(LungimeBat, LungimeBat + n);

	for (int i = 0; i < n - 2; i++) // Pentru ultimele 2 nr din sir nu vom putea forma un triunghi
	{
		for (int j = i + 1; j < n - 1; j++)  // Mergem pana la penultima cifra
		{
			int Dreapta = bsUltimul(n, LungimeBat, LungimeBat[i] + LungimeBat[j]);
			int Stanga = bsPrimul(n, LungimeBat, abs(LungimeBat[i] - LungimeBat[j]));

			if (Stanga <= j)
			{
				Stanga = j + 1;
			}

			int NrInInterval = Dreapta - Stanga + 1;

			if (NrInInterval < 0)
			{
				NrInInterval = 0;
			}

			contor += NrInInterval;
		}
	}

	fout << contor;
}