2019 ICPC NENA (Quebec) Regional Qualifier

Start

2019-10-26 05:00 AKDT

2019 ICPC NENA (Quebec) Regional Qualifier

End

2019-10-26 11:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -224 days 13:54:43

Time elapsed

6:00:00

Time remaining

0:00:00

Problem F
Voting Club's Election

Voting Club wants to elect a new president, and they decide to carry out the vote as follows. Say that $n$ members are candidates for president; then every other member of the club gets $n$ votes to distribute as they wish among the candidates. For example, if there are four candidates (let’s name them A, B, C, D) then the following are all legal ballots:

A2 B2 C0 D0 (this voter awarded two votes each to candidates A and B)
A0 B1 C1 D2 (this voter gave one vote to B and C, and two to D)
A0 B0 C0 D4 (this voter gave all votes to candidate D)

The tally (that is, the totals of the votes from all ballots) here is A2 B3 C1 D6. A candidate wins when the tally shows that they have more than half of the votes. In this example, no candidate has won, as there are $12$ votes, but no candidate has $7$ or more.

Should a tally contain no winner, the candidate with the least votes (in this example, C) is eliminated. Every ballot is reconsidered: all votes for the eliminated candidate on each ballot are transferred to that ballot’s leader(s). In our example, the new ballots would read:

A2 B2 D0 (C had no votes, so they are simply eliminated)
A0 B1 D3 (C’s lone vote is given to the ballot’s leader D)
A0 B0 D4 (Again C had no votes, so is simply eliminated)

Now the tally is A2 B3 D7, and candidate D has the majority of the votes, so D is the winner.

If, at any point, two or more candidates remain and they all have the same number of votes, then the election results are VOID.

It may be the case that the losing and/or the winning candidates are tied, so we handle those cases as follows. For example, suppose that four ballots, at some point, read:

A2 B0 C2 D3
A4 B2 C0 D1
A3 B2 C1 D1
A1 B1 C2 D3

The tally is A10 B5 C5 D8, so the losing candidates are tied. In this case, we eliminate all losing candidates and give their combined votes to each ballot’s leader. The result in this case would be:

A2 D5
A6 D1
A6 D1
A1 D6

for a tally of A15 D13, so A wins the election.

If the winning candidates on a ballot are tied, as in A4 B4 C1 D2 E4, and we need to distribute votes from losing candidate(s) to the winners, then each winner gets an equal share of the allotment. For example, if D were the eliminated candidate on this ballot, the new ballot would read

A14/3 B14/3 C1 E14/3

and thus your program will need to handle fractions.

Notes:

  • Assume all ballots are filled out correctly.

  • When they cast their ballots, voters may not give fractional votes.

  • The election will have at least one candidate.

  • All candidate names will be a single letter from the alphabet (so there will never be more than 26 candidates in a test file).

  • If there are ten or more candidates, then a legal initial ballot might contain a substring like B12 or D22.

Input

The first line is the number of ballots, the second line is the number of candidates, the third line shows the names of the candidates, and the rest of the lines are the ballots.

Output

  • VOID if the election ends with a fully tied tally (as in A8 B8 D8)

  • The WINNER’S NAME if there is a clear winner

Sample Input 1 Sample Output 1
5
4
B C D G
B0 C2 D2 G0
B2 C2 D0 G0
B0 C1 D1 G2
B1 C1 D1 G1
B0 C0 D3 G1
VOID
Sample Input 2 Sample Output 2
3
3
A B C
A1 B1 C1
A2 B1 C0
A0 B3 C0
B