Cod sursa(job #243871)

Utilizator drag0s93Mandu Dragos drag0s93 Data 14 ianuarie 2009 10:06:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
const int N=30001;
int n,ap[N],sum[N],v[801],nr;
int n1=0;
void citireap()
{
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&nr);
		ap[nr]++;
	}
}
void parcsum()
{
	for(int i=1;i<N;++i)
	{
		sum[i]=sum[i-1]+ap[i];
	}
}
void parcv()
{
	for(int i=1;i<N;++i)
		for(int j=1;j<=ap[i];++j)
			v[++n1]=i;
}
void calcul()
{
	int i=0,j=0,a=0,b=0,perechi=0;
	for(i=1;i<n1-1;++i)
		for(j=i+1;j<n1;++j)
		{
			if(v[i]+v[j]>=N)
				b=n1;
			else 
				b=sum[v[i]+v[j]];
			a=j;
			perechi=perechi+(b-a);
		}
	printf("%d\n",perechi);
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	citireap();
	parcsum();
	parcv();
	calcul();
	return 0;
}