Cod sursa(job #273567)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 8 martie 2009 19:05:36
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000
int n,nr=1;
struct milk{int a;}v[N];
int ap[N];
int compar(const void *p, const void *q)
{
	milk pp=*(milk*)p,qq=*(milk*)q;
	if (pp.a>qq.a) return 1;
	if (pp.a<qq.a) return -1;
	return 0;
}
void parcurg()
{
	int s=0,tri=0;
	for (int i=1;i<nr-1; ++i)
	{
		for (int j=i+1; j<nr; ++j)
		{
			s=v[i].a+v[j].a;
			int ok=0,p=0;
			for (int k=j+1; k<=nr&&s>=v[k].a; ++k)
			{
				p+=ap[v[k].a];
				ok=1;
			}
			if (ok)
				tri+=(ap[v[i].a]*ap[v[j].a]*p);
		}
	}
	printf("%d",tri);
}
void citire()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d",&v[nr].a);
		++ap[v[nr].a];
		if (ap[v[nr].a]==1)
			++nr;
	}
	if (v[nr].a==0||ap[v[nr].a]>1) --nr;
	qsort(v+1,nr,sizeof(v[0]),compar);
	//for (int i=1; i<=nr; ++i) printf("%d",v[i].a);
	parcurg();
}
int main()
{
	citire();
	return 0;
}