Cod sursa(job #178713)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 14 aprilie 2008 22:37:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<stdio.h>
#include<stdlib.h>
#define NMAX 30001
int x[NMAX];
int main()
{
int n,v[800]={0},i,j,k,nrtri=0,nr,nrmax=0;
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++){
	scanf("%d",&nr);
	if(nrmax<nr)nrmax=nr;
	x[nr]++;
	}
k=0;
for(i=1;i<=nrmax;i++)
	for(j=1;j<=x[i];j++){
		v[k]=i;
		k++;
		}

//qsort(v,0,n-1);
for(i=0;i<n-2;i++)
	for(j=i+1;j<n-1;j++){
		if(v[i]+v[j]<v[j+1]) continue;
		for(k=j+1;k<n;k++){
			   //	if(v[i]+v[k]<v[j]) continue;
			if(v[i]+v[j]<v[k]) break;
			nrtri++;
			}
		}
printf("%d",nrtri);
return 0;
}