Torneig de tennis P73160

Considereu un torneig de tennis amb $m$ participants, amb noms $x_1, x_2, \dots, x_m$, on $m$ és una potència de dos. A la primera ronda, $x_1$ juga contra $x_2$, $x_3$ juga contra $x_4$, …, 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_1$ ha guanyat a $x_2$, $x_3$ ha perdut amb $x_4$, $x_5$ ha guanyat a $x_6$, i $x_7$ ha guanyat a $x_8$. A la segona ronda $x_1$ i $x_4$ s’enfronten entre si (suposem que guanya $x_4$), i $x_5$ i $x_7$ s’enfronten entre si (suposem que guanya $x_7$). A la tercera i última ronda $x_4$ i $x_7$ s’enfronten entre si. Suposant que guanyi $x_4$, 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:

    string guanyador(const vector<string>& nom, const vector<bool>& guanya);

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_{\mbox{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.