Torneig de tennis P73160

Considereu un torneig de tennis amb m participants, amb noms x₁, x₂, …, x_m, on m és una potència de dos. A la primera ronda, x₁ juga contra x₂, x₃ juga contra x₄, …, i x_{m − 1} juga contra x_m. Els jugadors que perden queden eliminats, i el procés es repeteix amb els jugadors restants. Quan només queda un jugador, aquest és el guanyador del torneig.

Per exemple, sigui m = 8, i suposem que a la primera ronda x₁ ha guanyat a x₂, x₃ ha perdut amb x₄, x₅ ha guanyat a x₆, i x₇ ha guanyat a x₈. A la segona ronda x₁ i x₄ s’enfronten entre si (suposem que guanya x₄), i x₅ i x₇ s’enfronten entre si (suposem que guanya x₇). A la tercera i última ronda x₄ i x₇ s’enfronten entre si. Suposant que guanyi x₄, aquest és el campió. La figura següent mostra el campionat tot just descrit en forma d’arbre:

Cal que feu un procediment que, donats els noms dels jugadors i la taula de resultats, retorni el nom del guanyador del torneig:

El vector nom té mida m, on m és qualsevol potència de 2. Per a cada j entre 0 i m − 1, es té nom[j] = x_{j + 1}. Tots els noms són diferents.

Per exemple, aquesta podria ser la taula de noms del torneig descrit anteriorment:

El vector guanya té mida m − 1 i conté els resultats dels partits en el format següent: la primera ronda es guarda a les últimes m/2 posicions, la segona ronda es guarda a les m/4 posicions anteriors, la tercera ronda es guarda a les m/8 posicions anteriors, …, i el resultat de l’última roda (la final) es guarda a guanya[0]. El booleà de cada posició indica si el primer jugador (el de menor índex) ha guanyat al segon.

Aquesta seria la taula de resultats del torneig descrit anteriorment:

Per al torneig d’exemple, la resposta hauria de ser “Borg”.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.