Cod sursa(job #307792)

Utilizator cotofanaCotofana Cristian cotofana Data 24 aprilie 2009 23:03:37
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <cstdio>
#include <algorithm>
#define dim 810

using namespace std;

int n, v[dim];

int main()
{
	int i, j, k, log, lg;
	long long ct=0;
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);
	scanf("%d\n", &n);
	for (i=1; i<=n; i++) scanf("%d ", &v[i]);
	for (log=1; log<=n; log<<=1);
	sort(v+1, v+n+1);
	for (i=1; i<n-1; i++)
		for (j=i+1; j<n; j++)
		{
			for (lg=log, k=0; lg; lg>>=1)
				if (k+lg<=n && v[k+lg]<=v[i]+v[j])
					k+=lg;
			ct+=k-j;
		}
	printf("%lld\n", ct);
	return 0;
}