Cod sursa(job #2616086)

Utilizator Gliumarin negai Gliu Data 16 mai 2020 17:10:26
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n,a[809],k=0;

void sortare(){
	int nr1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			if(a[i]<a[j]){
				nr1=a[i];
				a[i]=a[j];
				a[j]=nr1;
			}
		}
	}
}

int cautare(int nr,int dreapta,int stinga){
	int mid;
	while(stinga < dreapta){
		mid= stinga +(dreapta-stinga) /2;
		if(a[mid]<=nr){
			stinga =mid+1;
		}else dreapta =mid;
	}
	return stinga - 1;
}

int main(){
in >>n;
for(int i=0;i<n;i++){
in >>a[i];	
}
sortare();
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
		k+=cautare(a[i]+a[j],n,j+1)-j;
		
		}
	}
	out <<k;
return 0;
}