Cod sursa(job #75596)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 3 august 2007 18:36:25
Problema Numarare triunghiuri Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXM=300;
long int n,bat[1001];
struct {long int ns,nd,posf,posl;} hash[MAXM+1];

long int max(long int a, long int b) {if (a>b) return a; return b;}
long int min(long int a, long int b) {if (a>b) return b; return a;}

void citire()
{
FILE *f=fopen("nrtri.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++)
	fscanf(f,"%ld",&bat[i]);
fclose(f);
}

void scrie(long int sol)
{
FILE *g=fopen("nrtri.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

void quick(long int li, long int lf)
{
long int i=li,j=lf,ii=0,jj=-1,auxi;
while (i<j)
	{
	if (bat[i]>bat[j])
		{
		auxi=bat[i];bat[i]=bat[j];bat[j]=auxi;
		auxi=ii;ii=-jj;jj=-auxi;
		}
	i+=ii;j+=jj;
	}
if (i-li>1) quick(li,i-1);
if (lf-i>1) quick(i+1,lf);
}

void init_hash()
{
long int i;
for (i=1;i<=n;i++)
	{
	if (hash[bat[i]].posf==0)
		{
		hash[bat[i]].posf=i;
		hash[bat[i]].posl=i;
		}
	else
		hash[bat[i]].posl=i;
	}
long int last=-1;
for (i=MAXM;i>=1;i--)
	{
	hash[i].nd=last;
	if (hash[i].posf!=0) last=i;
	}
last=-1;
for (i=1;i<=MAXM;i++)
	{
	hash[i].ns=last;
	if (hash[i].posf!=0) last=i;
	}
}

long int normalize(long int a) {if (a<0) return 0; return a;}

long int find(long int a, long int dir)
{
long int sol;
if (dir==1)
	{
	sol=hash[a].posf;
	if (sol==0)
		{
		if (hash[a].nd==-1) return n;
		sol=hash[hash[a].nd].posf;
		}
	return sol;
	}
else
	{
	sol=hash[a].posl;
	if (sol==0)
		{
		if (hash[a].ns==-1) return 1;
		sol=hash[hash[a].ns].posl;
		}
	return sol;
	}
}

int main()
{
citire();
long int sol=0,corectie,i,j,minim,maxim;
quick(1,n);
init_hash();
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
	{
	minim=max(bat[i]-bat[j],bat[j]-bat[i]);
	maxim=bat[i]+bat[j];
	corectie=0;
	if (minim<=bat[i]&&maxim>=bat[i]) corectie++;
	if (minim<=bat[j]&&maxim>=bat[j]) corectie++;
	sol+=normalize(find(min(MAXM,maxim),-1)-find(max(minim,1),1)+1)-corectie;
	}
scrie(sol/3);
return 0;
}