Pagini recente » Cod sursa (job #1008018) | Cod sursa (job #1911320) | Cod sursa (job #2762599) | Cod sursa (job #1934754) | Cod sursa (job #1536246)
#include <stdio.h>
using namespace std;
int n,v[801],aux[801],poz,k;
void interclasare(int st, int dr, int m)
{
int i=st,j=m+1,k=st;
while(i<=m&&j<=dr)
{
aux[k++] = v[i]<v[j] ? v[i++] : v[j++];
}
while(i<=m) aux[k++]=v[i++];
while(j<=dr) aux[k++]=v[j++];
for(k=st;k<=dr;k++)
v[k]=aux[k];
}
void mergesort(int st, int dr)
{
if(st==dr) return;
int m=(st+dr)/2;
mergesort(st,m);
mergesort(m+1,dr);
interclasare(st,dr,m);
}
void cautbin(int st, int dr)
{
if(st>dr) return;
int m=(st+dr)/2;
poz=m;
if(k>v[m]) cautbin(m+1,dr);
else if(k<v[m]) cautbin(st,m-1);
else return;
}
int main()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int a,b,i,j,n1,n2,nr=0;
scanf("%d",&n);
n1=n-1;n2=n-2;
for(i=0;i<n;i++)
scanf("%d",v+i);
mergesort(0,n-1);
for(a=0;a<n2;a++)
for(b=a+1;b<n1;b++)
{
k=v[a]+v[b];
cautbin(b+1,n-1);
if(v[poz]>k) poz--;
nr+=poz-b;
}
printf("%d",nr);
return 0;
}