Pagini recente » Statisticile problemei Polig | Rating Popan Razvan Calin (Razvanucu) | Istoria paginii preoni-2007 | Statistici Oprea Marina (marinaopr) | Cod sursa (job #121390)
Cod sursa(job #121390)
#include<stdio.h>
int n,v[801],a[801];
long s;
void merge(int st, int dr)
{
int ok,g,m,i,j,k;
if(st<dr)
{
m=(st+dr)/2;
merge(st,m);
merge(m+1,dr);
//interclasare st-->m m+1-->dr
i=st;
j=m+1;
ok=1;
k=0;
while(ok)
{
if(v[i]<v[j])
a[++k]=v[i++];
else
a[++k]=v[j++];
if (i>m || j>dr)
ok=0;
}
for(g=j;g<=dr;g++)
a[++k]=v[g];
for(g=i;g<=m;g++)
a[++k]=v[g];
k=0;
for(i=st;i<=dr;i++)
v[i]=a[++k];
}
}
int bs(int st, int dr)
{
int m;
m=(st+dr)/2;
if(st>dr) return m;
if(v[m]>=s)
if(v[m-1]>=s)
return bs(st,m-1);
else
return m-1;
else
return bs(m+1,dr);
}
int main()
{
int i,j,k;
long tr=0;
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
merge(1,n);
for(i=1;i<=n-2;i++)
for(j=i+1;j<n;j++)
{
s=v[i]+v[j]+1;
k=bs(j+1,n);
tr=tr+k-j;
}
printf("%ld",tr);
return 0;
}