Pagini recente » Cod sursa (job #1011999) | Cod sursa (job #1129156) | Cod sursa (job #2808206) | Cod sursa (job #539811) | Cod sursa (job #29592)
Cod sursa(job #29592)
#include<fstream.h>
int n,a[1000];
int divide(int p,int u)
{
int i,k,r,x=a[p];
i=p;
k=u;
while(i<k)
{
while(i<k && a[k]>=x) k--;
a[i]=a[k];
while(i<k && a[i]<=x) i++;
a[k]=a[i];
}
a[i]=x;
return i;
}
void qsort(int p,int u)
{
int m=divide(p,u);
if(m-1>p)
qsort(p,m-1);
if(m+1<u)
qsort(m+1,u);
}
int bsearch(int s,int k,int x)
{
int m=(s+k)/2;
if(s>=k)
return k;
if(x==a[m])
{
while(a[m]==x) m++;
return m-1;
}
else
{
if(x>a[m])
{
if(x<a[m+1])
return m;
else
return bsearch(m+1,k,x);
}
else
return bsearch(s,m-1,x);
}
}
int main()
{
int i,j,s=0,k;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i];
qsort(1,n);
for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
{
k=bsearch(j,n,a[i]+a[j]);
s+=k-j;
}
fout<<s<<"\n";
return 0;
}