Cod sursa(job #180289)

Utilizator tm_raduToma Radu tm_radu Data 16 aprilie 2008 20:42:31
Problema Medie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#define NM 9001

int n, m;
int i, j, k;
int v[NM];
int nrsol, p1, p2;

int Cbin1(int st, int dr);
int Cbin2(int st, int dr);
void Qsort(int st, int dr);

int main()
{
    freopen("medie.in", "r", stdin);
    freopen("medie.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; i++ ) scanf("%d", &v[i]);
    Qsort(1, n);
    
    for ( i = 1; i <= n; i++ )
		for ( j = i+1; j <= n; j++ )
            if ( (v[i]+v[j])%2 == 0 )
            {
                k = (v[i]+v[j])/2;
                p1 = Cbin1(1, n);
                p2 = Cbin2(1, n);
                if ( p1 != -1 && p2 != -1 ) 
                {
                    nrsol += (p2-p1+1);
                    if ( v[i] == v[j] ) nrsol -= 2;
                }    
            }    
    printf("%d\n", nrsol);
    return 0;
}

void Qsort(int st, int dr)
{
    int i = st-1, j = dr+1;
    do
    {
        do { i++; } while ( v[i] < v[st] );
        do { j--; } while ( v[st] < v[j] );
        if ( i <= j ) 
            k = v[i], v[i] = v[j], v[j] = k;
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}

int Cbin1(int st, int dr)
{
    if ( st == dr )
        if ( v[st] == k ) return st;
        else              return -1;
	int mij = (st+dr)/2;
	if ( k <= v[mij] ) return Cbin1(st, mij);
	else               return Cbin1(mij+1, dr);
}

int Cbin2(int st, int dr)
{
	if ( st == dr )
		if ( v[st] == k ) return st;
		else              return -1;
	int mij = (st+dr)/2+1;
	if ( k >= v[mij] ) return Cbin2(mij, dr);
	else               return Cbin2(st, mij-1);
}