Pagini recente » Cod sursa (job #1961446) | Cod sursa (job #1900573) | Cod sursa (job #2068631) | Cod sursa (job #1001185) | Cod sursa (job #2002349)
#include <fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[802];
void quicksort(int start, int stop)
{
int i=start,j=stop,nr;
nr=v[(i+j)/2];
do
{
while (i<stop && nr>v[i]) ++i;
while (j>start && nr<v[j]) --j;
if (i<=j)
swap(v[i++],v[j--]);
}while(i<=j);
if (j>start) quicksort(start,j);
if (i<stop) quicksort(i,stop);
}
int binara(int x, int lo, int hi)
{
int mi;
while (lo<hi)
{
mi=lo+(hi-lo+1)/2;
if (v[mi]<=x)
lo=mi;
else
hi=mi-1;
}
return lo;
}
int main()
{
fin >> n;
for (int i=1;i<=n;i++)
fin >> v[i];
quicksort(1,n);
int nrtri=0;
for (int i=1;i<=n-2;i++)
{
for (int j=i+1;j<=n-1;j++)
{
nrtri+=binara(i+j,j+1,n-1)-j;
}
}
fout << nrtri-1;
return 0;
}