Pagini recente » Cod sursa (job #1474943) | Cod sursa (job #40981) | Cod sursa (job #2207946) | Rating george (george321) | Cod sursa (job #118830)
Cod sursa(job #118830)
#include <stdio.h>
int i,n,j;
long ct,s,nraparitii;
int v[1000];
int part(int st, int dr)
{
int i,j,aux,s;
i=st; j=dr; s=-1;
while (i<j)
{
if (v[i]>v[j])
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
s=-s;
}
if (s==1) i++;
else j--;
}
return i;
}
void qsort(int st, int dr)
{
long p;
if (st<dr)
{
p=part(st,dr);
qsort(st,p-1);
qsort(p+1,dr);
}
}
int cauta(int a, int b)
{
int mij,st,dr;
st=a; dr=b;
while (st<=dr)
{
mij=(st+dr)/2;
if (v[mij]<=s)
{
st=mij+1;
if (v[mij+1]>s) return mij;
if (mij+1>n) return mij;
}
else dr=mij-1;
}
return 0;
}
void calc(int a, int b,int poz)
{
long vl;
s=a+b;
nraparitii=0;
vl=cauta(poz,n);
if (vl>poz) nraparitii=vl-poz;
ct+=nraparitii;
}
int main()
{
FILE*f=fopen("nrtri.in","r");
FILE*q=fopen("nrtri.out","w");
fscanf(f,"%d",&n);
ct=0;
for (i=1; i<=n; i++)
fscanf(f,"%d",&v[i]);
qsort(1,n);
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
calc(v[i],v[j],j);
fprintf(q,"%ld\n",ct);
return 0;
}