Cod sursa(job #240789)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 8 ianuarie 2009 18:25:13
Problema Medie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
//#include<algorithm>
//using namespace std;
int n,a[9001];
int cautbin(int x,int y){
	int st=x+1,dr=y-1,m;
	double nr=(double)(a[x]+a[y])/2;
	if((int)nr==(double)nr){
		while(st<=dr){
			m=st+(dr-st)/2;
			if(a[m]<nr)
			   st=m+1;
			else if(a[m]>nr)
			   dr=m-1;
			else if(a[m]==nr)
			   return m;}
		return 0;}
	else
		return 0;}
int divide(int p,int q){
	int st=p,dr=q,x=a[p];
	while(st<dr){
		while(st<dr&&a[dr]>=x)
			--dr;
		a[st]=a[dr];
		while(st<dr&&a[st]<=x)
			++st;
		a[dr]=a[st];
		a[st]=x;}
	return st;}
void qsort(int p,int q){
	int m;
	m=divide(p,q);
	if(m-1>p)
		qsort(p,m-1);
	if(m+1<q)
		qsort(m+1,q);}
void solve(){
	int i,j,l,z,k=0;
	scanf("%d",&n);
	for(i=1; i<=n; ++i)
		scanf("%d",&a[i]);
	qsort(1,n);
	for(i=1; i<n-1; ++i)
		for(j=i+2; j<=n; ++j){
			z=cautbin(i,j);
			if(z){
				for(l=z; a[l+1]==a[z]&&l<j-1; ++l);
				k+=l-z+1;}}
	printf("%d",k);}
int main(){
	freopen("medie.in","r",stdin);
	freopen("medie.out","w",stdout);
	solve();
	return 0;}