Cod sursa(job #2436814)

Utilizator tudosemihaitudose mihai tudosemihai Data 7 iulie 2019 13:03:56
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int a[801];
int n,pos;
int cautbin(int val)
{
	pos=0;
	for(int msk=1<<30; msk>0; msk/=2)
	{
		if(pos+msk<=n && a[pos+msk]<=val)
			pos+=msk;
	}
	if(a[pos]==val)
		return pos;
	else
		return -1;
}


int main()
{
	int i,j,k,cont=0,x;
	in >> n;

	for(i=1;i<=n;i++)
		in >> a[i];

	sort(a+1, a+n+1);

	for(i=1;i<=n-2;i++)
	{
		for(j=i+1;j<=n-1;j++)
		{
			x=a[i]+a[j];
			k=cautbin(x);
			cont=cont+pos-j;

		}
	}



	out << cont;
	return 0;
}