Pagini recente » Cod sursa (job #2935488) | Cod sursa (job #2472689) | Cod sursa (job #160833) | Cod sursa (job #1585571) | Cod sursa (job #75596)
Cod sursa(job #75596)
# 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;
}