#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define novi(x) x=(drvo *) malloc(sizeof(drvo))

typedef struct drvo
{
	int balans;
	struct drvo *levi;
	struct drvo *desni;
	float visina;
	char jmbg[14];
} drvo;

int dubina(drvo *p)
{
		if (!p) return 0;
		int dd=0,dl=0;
		if (p->levi)  dl=dubina(p->levi);
		if (p->desni) dd=dubina(p->desni);

		if (dd>dl)
		{
			return ++dd;
		}
		else return ++dl;
}
/*
void drotacija(drvo **p)
{
		drvo *pomd=*p;
		drvo *poml=pomd->levi;
		pomd->levi=poml->desni;
		poml->desni=pomd;
		*p=poml;
		poml->balans=dubina(poml->desni)-dubina(poml->levi);
		pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

void lrotacija(drvo **p)
{
		drvo *poml=*p;
		drvo *pomd=poml->desni;
		poml->desni=pomd->levi;
		pomd->levi=poml;
		*p=pomd;
		poml->balans=dubina(poml->desni)-dubina(poml->levi);
		pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

int dodaj(drvo **p,float visina,char jmbg[])
{
		int inkrement,rezultat;
		drvo *p1=*p;
		rezultat=0;
		if (!p1)
		{
			novi(p1);
			if (!p1)
			{
					printf("greska pri aloc");
					exit(1);
			}


		p1->visina=visina;
		strcpy(p1->jmbg,jmbg);
		p1->levi=p1->desni=NULL;
		p1->balans=0;
		rezultat=1;
		}
		else
		{
			if (visina > p1->visina) inkrement=dodaj(&(p1->desni),visina,jmbg);
			else inkrement=-dodaj(&(p1->levi),visina,jmbg);
			p1->balans+=inkrement;

			if (inkrement!=0 && p1->balans!=0)
			{
				if (p1->balans<-1)
				{
					if (p1->levi->balans<0) drotacija(&p1);
					else { lrotacija(&(p1->levi)); drotacija(&p1); }
				}
				else if (p1->balans>1)
				{
					if (p1->desni->balans>0) lrotacija(&p1);
					else {drotacija(&(p1->desni)); lrotacija(&p1); }
				}
				else rezultat=1;
			}
		}
		*p=p1;
		return rezultat;
}*/



void ispis(drvo *p)
{
		if (!p) return;
		ispis(p->levi);
		printf("%f %s\n",p->visina,p->jmbg);
		ispis(p->desni);
}

void lrotacija(drvo **p)
{
		drvo *poml=*p;
		drvo *pomd=poml->desni;
		poml->desni=pomd->levi;
		pomd->levi=poml;
		*p=pomd;
		poml->balans=dubina(poml->desni)-dubina(poml->levi);
		pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

void drotacija(drvo **p)
{
		drvo *pomd=*p;
		drvo *poml=pomd->levi;
		pomd->levi=poml->desni;
		poml->desni=pomd;
		*p=poml;
		poml->balans=dubina(poml->desni)-dubina(poml->levi);
		pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

int dodaj(drvo **p,float visina,char jmbg[])
{
	int inkrement;
	drvo *p1=*p;
	if (!p1)
	{
		novi(p1);
		if (!p1)
		{
			printf("aloc");
			exit(1);
		}
		p1->visina=visina;
		strcpy(p1->jmbg,jmbg);
		p1->balans=0;
		p1->levi=NULL;
		p1->desni=NULL;
	}
	else
	{
			if (visina>p1->visina) inkrement=dodaj(&p1->desni,visina,jmbg);
			else  inkrement=-dodaj(&p1->levi,visina,jmbg);
			p1->balans+=inkrement;

			if (p1->balans<-1)
			{
				if (p1->levi->balans<0) drotacija(&p1);
				else { lrotacija(&p1->levi); drotacija(&p1); }
			}
			else if (p1->balans>1)
			{
				if (p1->desni->balans>0) lrotacija(&p1);
				else { drotacija(&p1->desni); lrotacija(&p1); }
			}
	}
	*p=p1;
	return 1;
}
drvo *formiraj()
{
		drvo *p=NULL;
		int i,n;char jmbg[14];float visina;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%f",&visina);
			scanf("%s",jmbg);
			dodaj(&p,visina,jmbg);
		}
		return p;
}

/*Korišćenjem stabala napisati program koji na najefikasniji način pronalazi i štampa
matični broj najnižeg deteta koje se može voziti na ringišpilu, ukoliko se zna da je
ulaz na ringišpil dozvoljen samo deci iznad zadate visine.*/

void najnize(drvo *p,int k,drvo **min)
{
		if (!p) return;
		if (p->visina>k && p->visina<(*min)->visina) *min=p;
		/*else if (p->visina<k) najnize(p->desni,k,min);
		else if (p->visina>k) { */najnize(p->desni,k,min); najnize(p->levi,k,min);
}

void prosek(drvo *p,int *brojdece,float k,float *visine)
{
	if (!p) return;
	if (p->visina<k) { (*brojdece)++; *visine=(*visine)+p->visina; }
	prosek(p->levi,brojdece,k,visine);prosek(p->desni,brojdece,k,visine);
}

main()
{
	drvo *p=NULL,*min; novi(min);
	min->visina=200;
	p=formiraj();
	ispis(p);
	najnize(p,12,&min);
	if (min->visina==200) printf("nema");else printf("%s\n",min->jmbg);
	int brojdece=0;float visine=0;
	prosek(p,&brojdece,120,&visine);
	printf("%f",visine/brojdece);
}