Cod sursa(job #3294204)

Utilizator mihai.25Calin Mihai mihai.25 Data 18 aprilie 2025 23:12:51
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

#include <algorithm>

using namespace std;

ifstream fin ("nrtri.in");

ofstream fout ("nrtri.out");

int caut_bin (int val, int v[], int st, int dr) {

	int poz = dr + 1;

	while (st <= dr) {

		int mij = st + (dr - st) / 2;

		if (val < v[mij]) {

			poz = mij;

			dr = mij - 1;
		}
		else
			st = mij + 1;
	}

	return poz;
}

int main () {

	int n;

	fin >> n;

	int v[n + 1];

	for (int i = 1; i <= n; ++i)
		fin >> v[i];

	sort (v + 1, v + n + 1);

	int cnt = 0;

	for (int i = 1; i <= n - 2; ++i)
		for (int j = i + 1; j <= n - 1; ++j)	
		cnt += (caut_bin (v[i] + v[j], v, j + 1, n) - (j + 1));

	fout << cnt;

	return 0;
}