Cod sursa(job #352029)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 30 septembrie 2009 09:41:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
# include <fstream>

using namespace std;

int v[1<<17],n;

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

int modulo(int x){
	int nr;
	if(x<0){
		nr=x+(-2*x);
		return nr;
	}
	else{
		return x;
	}
}

void insertie(int x, int v[1<<17],int p){
	int j,i;
	j=0;
	while(v[j]<x){j++;}
	for(i=p+1;i>=j;i--){
		v[i]=v[i-1];
	}
	v[j]=x;
}

int caut1(int x){
	int i,pas;
	for(pas=1 ; pas<n ; pas<<=1);
	for(i=0 ; pas ; pas>>=1)
		if(i+pas<n && v[i+pas]<=x)
			i+=pas;
	return i;
}

int main(){
	int i,j,nrt=0,k;
	in>>n;
	for(i=0;i<n;i++){
		in>>v[i];
	}
	for(i=0;i<n-1;i++){
		insertie(v[i+1],v,i);
	}
	nrt=0;
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			k=v[j]+v[i];
			k=caut1(k);
			nrt+=k-j;
		}
	}
	out<<nrt<<"\n";
	return 0;

}