/* Šnečí maraton */
#include <stdio.h>
#include <stdlib.h>

struct uzel {
	int cislo;
	int vlevo;
	struct uzel *l,*p;
};

/* Do rekurzivní procedury předáváme ukazatel na ukazatel, protože nám to
umožní snadno připojit nový list k otci, ale také nám to zjednoduší vytváření
vůbec prvního uzlu, který nebude mít otce.  */
void
vloz_sneka(struct uzel **otec,struct uzel *koho,int poradi)
{
	struct uzel *kam=*otec;		/* Aktuální uzel.  */

	if(!kam){			/* Jsme v listu stromu?  */
		*otec=koho;		/* Připojíme nový vrchol k otci.  */
	} else {
		if(poradi<=kam->vlevo){	/* Vkládáme do levého podstromu.  */
			vloz_sneka(&kam->l,koho,poradi);
			kam->vlevo++;	/* Inkrementujeme počet vrcholů v levém podstromu.  */
		} else {
			vloz_sneka(&kam->p,koho,poradi-kam->vlevo-1);
		}
	}
}

void
vypis_sneky(struct uzel *snek)
{
	if(!snek)
		return;
	vypis_sneky(snek->l);
	printf("%d ",snek->cislo);
	vypis_sneky(snek->p);
}

void
dealokuj_sneky(struct uzel *snek)
{
	if(!snek)
		return;
	dealokuj_sneky(snek->l);
	dealokuj_sneky(snek->p);
	free(snek);
}

int main(void)
{
	int i,pocet;
	struct uzel *koren=NULL;
	
	printf("Zadej počet šneků: ");
	scanf("%d",&pocet);
	for(i=0;i<pocet;i++){
		int kolik;
		struct uzel *snek;

		printf("Kolik šneků s menším poř. číslem předběhl šnek č. %d? ",i+1);
		scanf("%d",&kolik);

		snek=calloc(1,sizeof(struct uzel));
		snek->cislo=i+1;
		vloz_sneka(&koren,snek,i-kolik);
	}

	printf("Pořadí šneků: ");
	vypis_sneky(koren);
	printf("\n");

	dealokuj_sneky(koren);

	return 0;
}