Pagini recente » Cod sursa (job #54034) | Cod sursa (job #709791) | Cod sursa (job #836822) | Cod sursa (job #466602) | Cod sursa (job #178272)
Cod sursa(job #178272)
#include<fstream.h>
int poz(int v[802], int p, int u)
{
int piv=v[p],aux;
while (p<u)
{
if (v[p]>v[u]) {
aux=v[p];
v[p]=v[u];
v[u]=aux;
}
if (piv==v[p]) u--;
else p++;
}
return p;
}
void quick (int v[802], int a, int b)
{
int k;
if (a<b) {
k=poz(v,a,b);
quick(v,a,k-1);
quick(v,k+1,b);
}
}
int cautbin(int v[802], int n, int val)
{
int p=1,i=0;
for (;p*2<=n;p*=2);
for (;p;p/=2)
if (i+p<=n && v[p+i]<=val) i+=p;
return i;
}
int main()
{
int v[802],n,i,j,nr=0;
ifstream f("nrtri.in");
f>>n;
for (i=1;i<=n;i++) f>>v[i]; f.close();
quick(v,1,n);
for (i=1;i<n-1;i++)
for (j=i+1;j<n;j++)
nr+=cautbin(v,n,v[i]+v[j])-j;
ofstream g("nrtri.out");
g<<nr;g.close();
return 0;
}