Cod sursa(job #2072052)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 21 noiembrie 2017 12:43:03
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>
#include <algorithm>
using namespace std;

int N, S, L[800];

int exista(int x, int a){
	int i, j, m;

	i=a; j=N-1;
	while (i<=j){
		m=(i+j)/2;
		if (L[m]>x)
			j=m-1;
		else
			i=m+1;
	}
	return j-a+1;
}

int main(){
	int i, j;

	ifstream fin ("nrtri.in");
	fin >> N;
	for (i=0; i<N; i++)
		fin >> L[i];
	fin.close();

	sort(L, L+N);

	for (i=0; i<N-2; i++)
		for (j=i+1; j<N-1; j++)
			S+=exista(L[i]+L[j], j+1);

	ofstream fout ("nrtri.out");
	fout << S << '\n';
	fout.close();

	return 0;
}