Pagini recente » Cod sursa (job #2877014) | Cod sursa (job #2855725) | Cod sursa (job #533977) | Cod sursa (job #1994709) | Cod sursa (job #342741)
Cod sursa(job #342741)
#include<stdio.h>
using namespace std;
#define dim 100001
int v[dim],y,x,n,tri=0;
int caut_bin2 (int z,int j)
{
int inceput=j+1,sfarsit=n,mij,nr=n+1;
while (inceput<=sfarsit)
{mij=inceput+(sfarsit-inceput)/2;
if(v[mij]<=z)
{
nr=mij;
sfarsit=mij-1;
}
else
inceput=mij+1;
}
return nr;
}
int caut_bin3 (int z,int j)
{
int inceput=j+1,sfarsit=n,mij,nr=n+1;
while (inceput<=sfarsit)
{mij=inceput+(sfarsit-inceput)/2;
if(v[mij]<=z)
{
nr=mij;
inceput=mij+1;
}
else
sfarsit=mij-1;
}
return nr;
}
unsigned long quicksort(unsigned long inceput, unsigned long ultimul)
{long long i,j,temp,aux,m=0;
i=inceput;
j=ultimul;
temp=v[(i+j)/2];
do
{while(v[i]<temp) i=i+1;
while(v[j]>temp) j=j-1;
if(i<j)
{aux=v[i]; v[i]=v[j]; v[j]=aux;m++;}
if(i<=j)
{j=j-1;
i=i+1;
}
}while(i<=j);
if(inceput<j) quicksort(inceput,j);
if(i<ultimul) quicksort(i,ultimul);
}
int main()
{
int x1,x2,i,j,s=0;
FILE *f=fopen("nrtri.in","r"), *g=fopen("nrtri.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
quicksort(1,n);
for(i=1;i<=n-2;i++)
for(j=i+1;j<=n-1;j++)
{
s=v[i]+v[j];
x1=caut_bin2(s,j);
if(x1!=n+1)
{ x2=caut_bin3(s,j);
if(x2!=n+1)
tri+=x2-x1+1;
}
}
fprintf(g,"%d\n",tri);
fclose(f);
fclose(g);
return 0;}