Cod sursa(job #1593923)

Utilizator valentin50517Vozian Valentin valentin50517 Data 8 februarie 2016 23:43:41
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>

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

bool comp(int a,int b) {return a < b;}
int N,A[1000],rs;
int cbin(int val){
	int step,i;
	for(step = 1;step < N;step<<=1);
	for(i = 0;step;step>>=1)
		if(i+step < N && A[i+step] <= val)
			i+=step;
	return i;
}

int main(){
	fin >> N;
	for(int i = 0;i<N;i++){
		fin >> A[i];
	} 
	
	sort(A,A+N,comp);
	for(int i = 0;i<N;i++)
		for(int j = i+1;j<N;j++){
			int k = cbin(A[i] + A[j]);
			if(k != i && k != j){
				rs+=k+bool(A[k] == A[i]+A[j]);
				if(i < k) rs--;
				if(j < k) rs--;
			}
		}
	fout << rs;
			
			
	return 0;
}