Cod sursa(job #1925428)

Utilizator Tudor27Tudor Iacob Tudor27 Data 13 martie 2017 10:23:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[5000],n;

int f(int a,int b){
	int m,n2;
	int pas;
	m=a+b;
	pas=1<<13;
	n2=-1;
	while(pas!=0){
		if(n2+pas<n && v[n2+pas]<=m){
			n2+=pas;
		}
		pas/=2;
	}
	//fout<<a<<" "<<b<<" "<<n2<<"\n";
	return n2;
}

int main()
{
	int i,x,k,s=0,ii;
	fin>>n;
	for(i=0;i<n;i++){
		fin>>v[i];
	}
	k=n-1;
	while(k!=1){
		i=0;
		while(i<k){
			if(v[i]>v[i+1]){
				x=v[i];
				v[i]=v[i+1];
				v[i+1]=x;
			}
			i++;
		}
		k--;
	}
	for(i=0;i<n-1;i++){
		for(ii=i+1;ii<n;ii++){
			s = s + f(v[i],v[ii]) - ii;
		}
	}
	fout<<s;
    return 0;
}