Cod sursa(job #118075)

Utilizator mithyPopovici Adrian mithy Data 23 decembrie 2007 01:36:11
Problema Medie Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#define NMax 9005

struct ceva
{	int nr, poz; } a[NMax];
int n;
FILE *f, *g;

void citire();
void rez();
int comp( const void *a, const void *b )
{
	return ( ((ceva*)a)->nr - ((ceva*)b)->nr );
}


int main()
{
	citire();
	rez();
	return 0;
}
void rez()
{
	int i, j, rez, st, dr, mij, poz, val=0;

	for (i=0; i<n-1; i++)
	for (j=i+1; j<n; j++)
	if ( (a[i].nr + a[j].nr) % 2 == 0 )
	{
		// daca totul e ok pana acum, dau o cautare binara
		rez = (a[i].nr+a[j].nr)/2;
		st = 0; dr = n-1; poz = -1; mij = -1;
		while ( st < dr )
		{
			mij = (st+dr)/2;
			if ( mij == st || mij == dr )
				break;

			if ( a[mij].nr == rez )
			{
				poz = mij;
				break;
			}
			if ( a[mij].nr < rez )
			{	st = mij; continue; }
			if ( a[mij].nr > rez )
			{	dr = mij; continue; }
		}

		if ( poz != -1 )
		{
			st = mij-1;
			dr = mij+1;
			if ( a[mij].poz != a[i].poz && a[mij].poz != a[j].poz )
				val++;
			while ( a[st].nr == a[mij].nr && st >= 0 )
			{
				if ( a[st].poz != a[i].poz && a[st].poz != a[j].poz )
					val++;
				st--;
			}
			while ( a[dr].nr == a[mij].nr && dr < n )
			{
				if ( a[dr].poz != a[i].poz && a[dr].poz != a[j].poz )
					val++;
				dr++;
			}
		}
	}

	fprintf( g, "%d\n", val );
}
void citire()
{
	int i;
	f = fopen( "medie.in", "rt" );
	g = fopen( "medie.out", "wt" );

	fscanf( f, "%d", &n );
	for (i=0; i<n; i++)
	{
		fscanf( f, "%d", &a[i].nr );
		a[i].poz = i;
	}

	qsort( a, n, sizeof(a[0]), comp );
}