Pagini recente » Cod sursa (job #2273682) | Cod sursa (job #846055) | Cod sursa (job #3161779) | Cod sursa (job #287759) | Cod sursa (job #528378)
Cod sursa(job #528378)
#include<fstream.h>
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[801],aux[801],c,ok,m,st,dr,nr,poz;
void interclas(int i,int m,int j)
{ int x=i,y=m+1,k=1,t=i;
while(x<=m&&y<=j)
if(v[x]<v[y]) aux[k++]=v[x++];
else aux[k++]=v[y++];
while(x<=m) aux[k++]=v[x++];
while(y<=j) aux[k++]=v[y++];
for(k=1;k<(j-i)+2;k++) v[t++]=aux[k];
}
void divimp(int i,int j)
{ if(i<j)
{int m=i+(j-i)/2;
divimp(i,m);
divimp(m+1,j);
interclas(i,m,j);
}
}
int main()
{ int i,j,k;
f>>n;
for(i=1;i<=n;i++) f>>v[i];
divimp(1,n);
for(k=3;k<=n;k++)
{j=k-1;
while(j>1)
{c=v[k]-v[j];
st=1; dr=j-1; ok=0;
while(st<=dr&&!ok)
{m=(st+dr)/2;
if(v[m]==c) ok=1,poz=m;
else if(v[m]<c) st=m+1;
else dr=m-1;
}
if(m>=j) m=j-1;
while(v[m]<c&&m<j) m++;
while(v[m-1]>=c&&m>1) m--;
nr=nr+j-m;
j--;
}
}
g<<nr<<'\n';
f.close(); g.close();
return 0;
}