Pagini recente » Cod sursa (job #992689) | Cod sursa (job #776311) | Cod sursa (job #3151084) | Cod sursa (job #2547593) | Cod sursa (job #2168416)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int nr, a[808], n;
int divide(int p, int q)
{
int st = p, dr = q, x = a[p];
while(st < dr){
while(st < dr && a[dr] >= x)
dr--;
a[st] = a[dr];
while(st < dr && a[st] <= x)
st++;
a[dr] = a[st];
}
a[st] = x;
return st;
}
void QSort(int p,int q)
{
int m = divide(p,q);
if(m - 1 > p)
QSort(p, m - 1);
if(m + 1 < q)
QSort(m + 1, q);
}
void afisare()
{
for(int i = 1;i <= n;i ++)
cout<<a[i]<<" ";
}
void citeste()
{
f>>n;
for(int i = 1;i <= n;i ++)
f>>a[i];
QSort(1, n);
}
int bsearch(int x,int s)
{
int dr = n, st = s, mid;
while(st<=dr)
{
mid = (st + dr) / 2;
if(a[mid] > x)
dr = mid - 1;
else st = mid + 1;
}
return dr - s;
}
void solve()
{
for(int i = 1; i <= n - 2;i++)
for(int j = i + 1;j <= n - 1;j++)
nr+=bsearch(a[i] + a[j],j);
}
int main()
{
citeste();
solve();
g<<nr;
return 0;
}