Cod sursa(job #2497440)

Utilizator sebimihMihalache Sebastian sebimih Data 22 noiembrie 2019 17:48:09
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 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
{1}
		[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 = j + 1;

			int NrInInterval = Dreapta - Stanga + 1;

			contor += NrInInterval;
		}
	}

	fout << contor;
}