Pagini recente » Cod sursa (job #1071819) | Cod sursa (job #54728) | Cod sursa (job #2463982) | Cod sursa (job #2777935) | Cod sursa (job #394954)
Cod sursa(job #394954)
#include <fstream>
using namespace std;
#include <algorithm>
ifstream in ( "nrtri.in" );
ofstream out ( "nrtri.out" );
int N, v [ 1 << 10 ], cnt;
bool comp ( int a, int b )
{
return a < b;
}
/*void BS ( int I, int J )
{
for ( int i = N; i > J; --i )
if ( v [ i ] >= v [ I ] && v [ i ] >= v [ J ] && v [ i ] <= v [ I ] + v [ J ] )
{
cnt += i - J;
break;
}
}*/
void BS ( int I, int J )
{
int i, lg,logN;
for (logN = 1; logN <= N; logN <<= 1);
for (lg = logN, i = 0; lg; lg >>= 1)
if (i + lg <= N && v [ i + lg ] >= v [ I ] && v [ i + lg ] >= v [ J ] && v [ i + lg ] <= v [ I ] + v [ J ])
i += lg;
if ( v [ i ] >= v [ I ] && v [ i ] >= v [ J ] && v [ i ] <= v [ I ] + v [ J ] )
cnt += i - J;
}
int main ()
{
in >> N;
for ( int i = 1; i <= N; ++i )
in >> v [ i ];
sort ( v + 1, v + N + 1, comp );
for ( int i = 1; i < N; ++i )
for ( int j = i + 1; j <= N; ++j )
BS ( i, j );
out << cnt;
return 0;
}