Tennis tournament P73160


Statement
 

pdf   zip   main.cc

html

Consider a tennis tournament with m participants with names x1, x2, …, xm, where m is a power of two. In the first round x1 plays against x2, x3 plays against x4, …, and xm − 1 plays against xm. 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 x1 defeats x2, x3 loses against x4, x5 defeats x6, and x7 defeats x8. In the second round x1 plays against x4 (suppose that x4 wins), and x5 plays against x7 (suppose that x7 wins). In the third and last round x4 plays against x7. Assuming that x4 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] = xj + 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++