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 \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.