Consider a tennis tournament with m participants
with names x_{1}, x_{2}, …, x_{m}, where m is a power of two.
In the first round x_{1} plays against x_{2}, x_{3} plays against x_{4},
…, and x_{m − 1} plays against x_{m}.
The players that lose are eliminated, and the process is
repeated with the remaining players.
When only a player remains, this is the winner of the tournament.

For instance, let m = 8,
and suppose that in the first round x_{1} defeats x_{2},
x_{3} loses against x_{4}, x_{5} defeats x_{6}, and x_{7} defeats x_{8}.
In the second round x_{1} plays against x_{4} (suppose that x_{4} wins),
and x_{5} plays against x_{7} (suppose that x_{7} wins).
In the third and last round x_{4} plays against x_{7}.
Assuming that x_{4} wins, this is the champion.
The following figure shows the championship just described:

Write a procedure that, given the names of the players and the table of results, returns the name of the winner of the tournament:

string winner(const vector<string>& name, const vector<bool>& win);

The vector *name* has size m, where m is any power of 2.
For each *j* between 0 and m − 1, we have *name[j]* = x_{j + 1}.
All the names are different.

For instance, this could be the table of names of the tournament previously described:

The vector *win* has size m − 1 and contains all the results of the matches:
the first round is stored in the last m/2 positions,
the second round is stored in the m/4 previous positions,
the third round is stored in the m/8 previous positions, …,
and the result of the last round (the final) is stored in *win[0]*.
The boolean of each position indicates
if the first player (the one with the smallest index)
has won against the second one.

This would be the table of results of the tournament previously described:

For the example tournament, the answer should be “Borg”.

Observation You only need to submit the required procedure; your main program will be ignored.

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++