Girls Invitational '18 J4 - Elections in Ada Land

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Problem type

The country of Ada Land is holding their general election!

Ada Land uses a different voting system than Canada, and you have been tasked with figuring out the winners.

In the Ada Landian elections, one election is held for each of the \(N\) ridings. Each riding elects one candidate. Each election has \(V_i\) voters and \(C_i\) candidates.

Each of the \(V_i\) voters writes the names of all \(C_i\) candidates in order of preference on their ballot.

In order to be elected, a candidate must get at least \(50\%\) of the votes. If nobody has enough votes, the candidate in last place is eliminated, and their voters ballots are transferred to their next non-eliminated choice.

In the case of a tie during any point in the count, the candidate whose name was listed first in the list of candidates ranks higher.

Input Specification

The first line contains \(N\ (1 \le N \le 500)\), the number of elections to be held. The input for \(N\) elections follows.

Each election input start with \(C_i\), the number of candidates in the \(i^{th}\) election. \(1 \le C_i\le 1000\).

The next line contains \(C_i\) alphanumeric names, separated by spaces. It is guaranteed that in any single election, no two candidates will have the same name.

The next line contains \(V_i\), the number of voters in the \(i^{th}\) election. \(1 \le V_i \le 1000\).

The next \(V_i\) lines contain the ballot of each voter. Each ballot is a list of all candidate’s names separated by a single space. Names are in order of the voter’s preference, with the most preferred candidate’s name first and the least preferred candidate’ name last.

Additionally: \[\displaystyle N \times \prod_{i=1}^N C_i \times \prod_{i=1}^N V_i \le 1\ 000\ 000\]

Output Specification

Output the names of the elected candidates in the same order that the elections were given in the input.

Sample Input

2
4
Ada Lovelace Grace Hopper
7
Ada Lovelace Grace Hopper
Ada Lovelace Grace Hopper
Ada Lovelace Grace Hopper
Grace Ada Lovelace Hopper
Grace Lovelace Ada Hopper
Lovelace Ada Grace Hopper
Lovelace Ada Grace Hopper
3
C B A
3
A B C
B A C
C B A

Sample Output

Ada
B

Comments

There are no comments at the moment.