Pagini recente » Cod sursa (job #2093408) | Cod sursa (job #2564300) | Cod sursa (job #523263) | Cod sursa (job #1817736) | Cod sursa (job #362047)
Cod sursa(job #362047)
#include <stdio.h>
int v[801],aux[801],n,q;
void inter(int l,int mid,int r)
{
int i=l,j=mid+1,x=0;
do
{
++x;
if (((v[i]<v[j])&&(i<mid+1))||(j>r))
{
aux[x]=v[i];
++i;
}
else
{
aux[x]=v[j];
++j;
}
}
while (x<r-l+1);
for (i=l;i<r+1;i++) v[i]=aux[i-l+1];
}
void merge(int l,int r)
{
if (l==r) return;
int mid=((l+r)/2);
merge(l,mid);
merge(mid+1,r);
inter(l,mid,r);
}
int cautbin(int x)
{
int lo, hi, mid, last = 0;
for (lo = q+1, hi = n; lo <= hi; )
{
mid = lo + (hi-lo) / 2;
if (v[mid] <= x) last = mid, lo = mid+1;
else hi = mid-1;
}
return last;
}
int main()
{
int a,b,x,z=0,i;
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for (q=1;q<n+1;q++) scanf("%d",&v[q]);
merge(1,n);
q=0;
for (i=1;i<n-1;i++)
for (q=i+1;q<n;q++)
{
x=cautbin(v[i]+v[q]);
if (x>q) z+=x-q;
}
printf("%d",z);
return 0;
}