Cod sursa(job #20742)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 21 februarie 2007 23:55:31
Problema Numarare triunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
long int sol;
int x[801],n,i,j,k,aux;
int heapdown(int ic,int ls)
{  int is,aux;
   if(ic>(ls/2))return 0;
   is=2*ic;if(ic<(ls/2)) if(x[is]<x[is+1]) is++;
   if(x[ic]<x[is]) {aux=x[ic];x[ic]=x[is];x[is]=aux;heapdown(is,ls);}
   return 0;
}
int main()
{
	FILE *f=fopen("nrtri.in","r");
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
	fscanf(f,"%d",&x[i]);
	fclose(f);
	for(i=n/2;i>=1;i--)
	heapdown(i,n);
	for(k=n;k>=1;k--)
	{ aux=x[k];x[k]=x[1];x[1]=aux;heapdown(1,k-1);}
	for(i=1;i<=n-2;i++)
	for(j=i+1;j<=n-1;j++)
	{ k=n;while(x[i]+x[j]<x[k])k--;
	  sol=sol+(k-j);
	}
	f=fopen("nrtri.out","w");
	fprintf(f,"%ld",sol);
	fclose(f);
	return 0;
}