The country of Whuddadumpia is holding elections. Citizens vote by submitting a ballot that lists their first choice, second choice, third choice, and so on. Your job is to write a program that tabulates the ballots and determines a winner. There are a number of different possible voting algorithms, none of which is perfect. The one used by Whuddadumpia is as follows. Count up the first-choice votes for each candidate; the one with the most votes wins. If there is a tie between two or more candidates, use the number of second-choice votes (among all ballots) to resolve the tie. If there is still a tie, use third-choice votes, and so on.
The input consists of one or more elections. Elections begin with a list of numbered candidates, one per line, as shown in the examples. Candidates are numbered sequentially starting from 0; there are at most ten candidates. Following the candidates are one or more ballots, one per line. Ballots list a voter's first choice, second choice, third choice, and so on. Not all candidates need be listed in a ballot. If a ballot lists a candidate more than once or lists a nonexistent candidate, then it is invalid and must be ignored. For each election, output a single line containing the name of the winner, or --none-- if there is no winner.
Whuddadumpia only has 1000 citizens that are registered to vote.
Input must be read from the file "prob40.in", and output must be
written to the file "prob40.out". All output to the screen will be
ignored.
<BOF> #0 Tweety #1 Krusty #2 Barney #3 Grumpy 2130 123 2102 0 13 <EOF>
Krusty
A version of this problem originally appeared in the 1993 ACM East-Central Regionals.
Dr. Eric Shade