Cod sursa(job #340627)

Utilizator prdianaProdan Diana prdiana Data 15 august 2009 19:53:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAXN 816

using namespace std;

vector<int> a;
int n,nrsol;

void bsearch(int key,int ilo)
{
	int hi = n,m,lo = ilo,am;
	while (lo<=hi)
	{
		m = (lo+hi)/2;
		if (a[m] <=key)
		{
			nrsol++;
			am = m;
			while (am>ilo)
			{
				am--;
				nrsol++;
			}
			while (a[m]<=key)
			{
				if (m<n-1)
				{
					m++;
				}
				else
				{
					return;
				}
				if (a[m]<=key)
				{
					nrsol++;
				}
			}
			return;
		}
		else if (m>=ilo)
		{
			hi = m-1;
		}
		else
		{
			return;
		}

	}
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);

	int i,j,aux;
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d",&aux);
		a.push_back(aux);
	}
	sort(a.begin(),a.end());
	for (i=0;i<n;i++)
	{
		for (j=i+1;j<n-1;j++)
		{
			bsearch(a[i]+a[j],j+1);
		}
	}
	printf("%d",nrsol);
	return 0;
}