Cod sursa(job #59871)

Utilizator DastasIonescu Vlad Dastas Data 10 mai 2007 21:25:46
Problema Medie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#define maxn 9001
#define maxval 7001

FILE *in = fopen("medie.in","r"), *out = fopen("medie.out","w");

int n;
int a[maxn], f[maxval] = {0};

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 0; i < n; ++i )
        fscanf(in, "%d", &a[i]);
}

int partition(int top, int bottom)
{
     int x = a[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
        do
        {
            --j;
        } while ( x < a[j] );

        do
        {
            ++i;
        } while ( x > a[i] );

        if ( i < j )
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
     } while ( i < j );

     return j;
}

void quicksort(int top, int bottom)
{
    int middle;
    if ( top < bottom )
    {
        middle = partition(top, bottom);
        quicksort(top, middle);
        quicksort(middle+1, bottom);
    }

    return;
}

int main()
{
    read();
    quicksort(0, n-1);

    int sol = 0;
    int v[maxval] = {0};

    for ( int i = 0; i < n-1; ++i )
    {
        ++f[a[i]];
        for ( int j = i+1; j < n; ++j )
            if ( ((a[i] + a[j]) & 1) == 0 )
                ++v[(a[i]+a[j])>>1];
    }

    ++f[a[n-1]];

    for ( int i = 0; i < n; ++i )
        if ( v[a[i]] )
            sol += v[a[i]] - f[a[i]] + 1;

    fprintf(out, "%d\n", sol);

    return 0;
}