Cod sursa(job #1621580)

Utilizator adu18sptAndrei Mircea adu18spt Data 29 februarie 2016 20:05:28
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<algorithm>
#include<iostream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
unsigned n,a[1000],i,j,sum,c,nr;

unsigned step=1<<12,index;

unsigned cautbin(unsigned val,unsigned start);

int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
	}
	sort(a+1,a+n+1);
	
	for(i=1;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			sum=a[i]+a[j];
			
			nr+=cautbin(sum,j)-j;
			
		}
	}
	fout<<nr+1;
	return 0;
}

unsigned cautbin(unsigned val,unsigned start)
{
	for(;step;step>>=1)
	{
		index=start+step;
		if(index>=n)
		continue;
		if(a[index]<val)
		start=index;
	}
	return start;	
}