Girls Invitational '19 J4 - Who Will Win?

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

Here at Mackenzie, we take great pride in our sports teams. Since winter has come to an end, our school's attention has shifted to the basketball team. They'll be competing for the best team in our region as they hope to make provincials.

In MCPT, we like to analyze other schools and assign power levels to each high school basketball team in our region, including ourselves. There is an upcoming single elimination round robin tournament where 2^N teams will be competing.

A simple single elimination round robin tournament consists of an even number of teams in which each team competes in a series of rounds to determine the winner. The first round consists of the \frac{\text{number of teams}}{2} matches. The second round consists of the winners of those matches facing off against each other. This continues until there is one team left, who is declared the winner. Note that for this problem, the number of teams will always be a power of 2. The teams will be listed in their round robin order as shown above.

For example, if the teams are listed as:

William Lyon Mackenzie C.I.
Earl Haig Secondary School
Marc Garneau C.I.
Martingrove C.I.

Then the first round will be William Lyon Mackenzie C.I. vs. Earl Haig Secondary School and Marc Garneau C.I. vs. Martingrove C.I.

Each executive gives their own list of team power levels, with each team having a score from 1 to 100.

The victor of a match is determined by the average of every executives' power ranking for that team. The team with the higher average power ranking will win the match. If two teams have the same power ranking, the team who is listed first wins. For example, if Marc Garneau C.I. and Martingrove C.I. from above have the same average power ranking, Marc Garneau C.I. would win.

Given the teams participating and their power rankings, we want you to write a program that determines which team will win the tournament.

Input Specification

The first line contains two integers 2^N (1 \le N \le 15), the number of teams, and S (1 \le S \le 20), the number of MCPT executives betting.

The next 2^N lines will contain a unique name of a team competing. Names will contain only alphanumerical characters, spaces, and periods. Names will consist of at most 50 characters.

The next S lines will each contain 2^N integers, P (1 \le P \le 100), representing the power ranking of each team in the order they were listed in.

Output Specification

On the first line, print the two teams in the final match, from top to bottom in the bracket with vs. in between the two names.
On the second line, print the name of the winning team.

Sample Input 1

2 1
William Lyon Mackenzie C.I.
Earl Haig Secondary School
35 43

Sample Output 1

William Lyon Mackenzie C.I. vs. Earl Haig Secondary School
Earl Haig Secondary School

Sample Input 2

8 6
Marc Garneau C.I.
Martingrove C.I.
A Y Jackson Secondary School
Oakwood C.I.
Georges Vanier Secondary School
Winston Churchill C.I.
York Mills C.I.
Forest Hill C.I.
23 32 65 77 45 42 65 87
45 43 76 12 64 32 32 45
53 34 79 12 93 61 41 56
13 64 89 53 31 64 56 42
64 53 52 76 43 31 67 42
12 45 67 34 32 56 76 85

Sample Output 2

A Y Jackson Secondary School vs. Forest Hill C.I.
A Y Jackson Secondary School


There are no comments at the moment.