Cod sursa(job #627697)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 30 octombrie 2011 14:16:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "nrtri.in"
#define file_out "nrtri.out"

int N,V[10100],ans;

int cautare(int X){
	
	int i,step;
	for (step=1;step<N;step<<=1);
	     for (i=0;step;step>>=1)
			  if (i+step<=N && V[i+step]<=X) 
				   i+=step;
	return i;
}	

int main(){
	
	
	int i,p,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%d", &V[i]);
	sort(V+1,V+N+1);
	
	ans=0;
	for (i=1;i<N;++i)
		 for (j=i+1;j<=N;++j){
			 p=cautare(V[i]+V[j]);
			 //printf("%d %d\n", p,j);
			 ans+=p-j;
		 }
		 
	printf("%d\n", ans);

	return 0;
	
}