Pagini recente » Cod sursa (job #1595762) | Cod sursa (job #344829) | Cod sursa (job #2895375) | Cod sursa (job #2770825) | Cod sursa (job #2064812)
#include <stdio.h>
#include <stdlib.h>
int n,a[801],poz,s;
int Pivotare(int st,int dr)
{ int aux,i,j,p=(st+rand()%(dr-st+1)+st+rand()%(dr-st+1)+st+rand()%(dr-st+1))/3;
//swap(a[p],a[dr]);
aux=a[p];
a[p]=a[dr];
a[dr]=aux;
i=st-1;
for(j=st;j<=dr;j++)
if(a[j]<a[dr])
{ i++;
//swap(a[i],a[j]);
aux=a[i];a[i]=a[j];a[j]=aux;
}
//swap(a[i+1],a[dr]);
aux=a[i+1];a[i+1]=a[dr];a[dr]=aux;
return i+1;
}
void QuickSort(int st,int dr)
{ if(st<dr)
{ int p=Pivotare(st,dr);
QuickSort(st,p-1);
QuickSort(p+1,dr);
}
}
int Cautbin(int p,int x)
{ int st=p,dr=n,mij;
while(st<=dr)
{ mij=st+(dr-st)/2;
if(a[mij]==x&&a[mij+1]!=x) return mij;
else if(a[mij]==x&&a[mij+1]==x) ++st;
else if(a[mij]<x) st=mij+1;
else if(a[mij]>x) dr=mij-1;
}
if(a[mij]>x) return mij-1;
if(a[mij]<x) return mij;
}
int main()
{ int i,j;
FILE *f,*g;
f=fopen("nrtri.in","r");
g=fopen("nrtri.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",a+i);
QuickSort(1,n);
for(i=1;i<=n-2;++i)
for(j=i+1;j<=n-1;++j)
{ poz=Cautbin(j+1,a[i]+a[j]);
s+=poz-(j+1)+1;
}
fprintf(g,"%d",s);
return 0;
}