Pagini recente » Cod sursa (job #1714553) | Cod sursa (job #992297) | Cod sursa (job #2078505) | Cod sursa (job #1525970) | Cod sursa (job #122150)
Cod sursa(job #122150)
#include <stdio.h>
#define in "medie.in"
#define out "medie.out"
#define NMAX 9005
int V[NMAX];
int n, VAL, nrsol, FIND;
void QSort(int,int);
int BS( int X, int _init, int _final, int P);
int main()
{
freopen( in, "r", stdin );
freopen ( out, "w", stdout );
scanf( "%d", &n );
int i,j;
for ( i = 1; i <= n; ++i )
scanf( "%d", &V[i] );
QSort( 1, n );
for ( i = 1; i <= n; ++i )
{
VAL = (V[i]<<1);
for ( j = 1; j <= n; ++j )
{
if ( i == j ) continue;
FIND = VAL - V[j];
nrsol += BS( FIND, j+1, n, i);
}
}
printf( "%d\n", nrsol );
return 0;
}
int BS( int X, int _init, int _final, int P)
{
bool ok = false;
bool ok2 = false;
int poz1, poz2, count, st, dr, mij;
st = _init, dr = _final;
while ( st <= dr )
{
mij = ((st+dr)>>1);
if ( X < V[mij] ) dr = mij-1;
else if ( X > V[mij] ) st = mij+1;
else if ( X == V[mij] )
{
ok = true, poz2 = mij, st = mij+1;//ultima poz din sir
if ( mij == P ) ok2 = true;
}
}
st = _init, dr = _final;//optimizare aici ar merge!!! ( pornesc din st si dr aflatia anterior )
if ( !ok ) return 0;
while ( st <= dr )
{
mij = ((st+dr)>>1);
if ( X < V[mij] ) dr = mij-1;
else if ( X > V[mij] ) st = mij+1;
else if ( X == V[mij] )
{
poz1 = mij, dr = mij-1;//prima poz din sir
if ( mij == P ) ok2 = true;//nu-s asa sigur pe asta
}
}
if ( !ok ) return 0;
else
{
if ( ok2 == true ) return poz2-poz1;
else return poz2-poz1+1;
}
}
void QSort( int st, int dr )
{
int i = st-1, j = dr+1;
int pivot = V[st];
do
{
do { i++; } while ( V[i] < pivot );
do { j--; } while ( V[j] > pivot );
if ( i <= j )
{
int aux = V[i];
V[i] = V[j];
V[j] = aux;
}
} while ( i <= j );
if ( i < dr ) QSort( i, dr );
if ( st < j ) QSort( st, j );
}