Pagini recente » Cod sursa (job #1091770) | Cod sursa (job #1884565) | Cod sursa (job #443738) | Cod sursa (job #2700104) | Cod sursa (job #911109)
Cod sursa(job #911109)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[801],n,nr;
void schimb(int i,int j)
{
int aux;
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
void sort(int l,int h)
{
int piv,i=l,j=h;
piv=(l+h)/2;
piv=v[piv];
while(i<=j)
{
while(v[i]<piv)
i++;
while(v[j]>piv)
j--;
if(i<=j)
schimb(i++,j--);
}
if(i<h)
sort(i,h);
if(j>l)
sort(l,j);
}
int caut(int x)
{
int i=0,pas=1<<9;
while(pas!=0)
{
if(i+pas<=n && v[i+pas]<x)
i+=pas;
pas/=2;
}
return i;
}
void solve()
{
int x,y,z,d;
for(x=n;x>2;x-=d)
{
y=caut(v[x]);
d=x-y;
for(;y>1;y--)
{
z=v[x]-v[y];
if(z<=v[y])
nr+=d*(y-caut(z)-1);
else
break;
}
}
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>v[i];
sort(1,n);
solve();
out<<nr;
return 0;
}