Cod sursa(job #2436817)

Utilizator GheteaMihaiGhetea Mihai GheteaMihai Data 7 iulie 2019 13:06:36
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 cin ("nrtri.in");
ofstream cout ("nrtri.out");

short a[2001];
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;
		return -1;
}


int main()
{
	int k,cont=0,x;
        cin >> n;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1, a+n+1);
	for(int i=1;i<=n-2;i++)
	{
		for(int j=i+1;j<=n-1;j++)
		{
			x=a[i]+a[j];
			k=cautbin(x);
			cont=cont+pos-j;
		}
	}
	cout << cont;
	return 0;
}