Cod sursa(job #3361490)

Utilizator Darkillgo22Marcus Darkillgo22 Data 24 iulie 2026 17:49:19
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
//incercam fara sortare eficienta, altfel facem cu sort din algorithm
#include <fstream>

using namespace std;

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

int main() {
	int n, l[800], i, j, nr = 0, s;

	fin >> n;
	for (i = 0; i < n; ++i)
		fin >> l[i];

	//sortare
	for (i = 1; i < n; ++i) {
		int x = l[i];
		for (j = i - 1; j >= 0 && l[j] > x; --j)
			l[j+1] = l[j];
		l[j+1] = x;
	}

	//numarare cu cautare binara pe cel mai mic termen mai mare sau egal cu l[i] - l[j].
	for (i = n - 1; i > 1; --i) {
		for (j = i - 1; j > 0; --j) {
			s = l[i] - l[j];
			if (l[j-1] >= s) {
				int lt = 0, rt = j - 1, mid;
					while (lt <= rt) {
						mid = (lt + rt) / 2;
						if (l[mid] >= s)
							rt = mid - 1;
						else if (l[mid] < s)
							lt = mid + 1; //lt va da poz celui mai mic nr >= s
					}
				nr += j - lt;
			}
			else 
				break;
		}
	}

	fout << nr;
		
	
}