Cod sursa(job #255860)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 10 februarie 2009 20:01:06
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <stdlib.h>

const int N = 801;

int n,v[N],nrt=0;

void citire()
{
	scanf ("%d",&n);
	for (int i = 1; i <= n; ++i)
		scanf ("%d",&v[i]);
}

int comparare (const void *p, const void *q)
{
	int x = *(int*)p, y = *(int*)q;
	if (x < y)
		return -1;
	if (x > y)
		return 1;
	return 0;
}

void sortare()
{
	qsort(v+1,n,sizeof(v[0]),comparare);
}

int cautare_binara(int nr,int l1)
{
	int l2 = n;
	while ((v[l1] != nr)&&(v[l2] != nr)&&(l1 + 1 < l2))
		if (v[(l1+l2)/2] > nr)
			l2 = (l1+l2)/2;
		else l1 = (l1+l2)/2;
	return l1;
}

void cautare()
{
	for (int i = 1; i < n-1; ++i)
		for (int j = 1; j < n; ++j)
		{
			nrt += cautare_binara(i+j,j) - j;
		}
}

void afisare()
{
	printf ("%d",nrt);
}

int main()
{
	freopen ("nrtri.in","r",stdin);
	freopen ("nrtri.out","w",stdout);
	citire();
	sortare();
	cautare();
	afisare();
}