Due to massive confusion on the last County election, the Supervisors
appointed a committee to recommend changes inthe election process.
The committee's first choice was to change to an 'instant runoff'
system in which each voter ranks all candidates in a race, specifying
1st, 2nd, 3rd, etc. choices for candidates. This has the advantage of
saving the county money, since only one election is required, since
there no need for both a primary and a general election. However,
focus groups of county voters disliked the idea of having to rank all
candidates.
The voter focus groups preferred listing head-to-head contests between
every possible pairing of candidates for an office. In this model,
for four candidates, A, B, C, and D, the ballot lists the following
pairings:
A vs. B, A vs. C, A vs. D
B vs. C, B vs. D
C vs. D
The voter marks his/her preference for each of these 'forced choice'
scenarios.
This model rapidly becomes unwieldy as the race grows beyond four
candidates. A five-candidate race would have ten head-to-head
pairings. Therefore, if more than four candidates qualify for a race,
a primary election will be held in which the top four candidates by
plurality will advance to the general election. The resulting
head-to-head general election will not exceed six pairings.
In the order they are to be applied, the rules for winning are:
- If a candidate beats all opponents, that candidate wins.
- Add up the total votes for a candidate in all the head-to-head
races. Drop the candidate with the fewest votes. If this is a tie,
remove all candidates with that total (unless that is ALL the
candidates). If there are any candidates remaining, remove the
contests not involving them and start over with step 1.
- Declare a tie, the winner will be decided by a log rolling contest
Input
Input is a series of races terminated by end-of-file. Each reace
starts with the name of the office, an alphanumeric string on 1 line.
The next line will be the votes for each candidate in that race. Ther
are three possible formats: 1, 3, or 6 pairs of numbers. Each number
is separated by a blank. Each line will be at most 80 characters
long.
n12 n21
n12 n21 n13 n31 n23 n32
n12 n21 n13 n31 n14 n41 n23 n32 n24 n42 n34 n43
Where nij is the number of votes for candidate i against
candidate j in that head-to-head contest.
Output
Print two lines for each contest. Print the name of the office on the
first line. Print the candidate number of the winner on the second
line. IF there is a tie, print the candidate numbers involved in the
tie, sorted by candidate number (lowest first) and separated by one
space each.
Sample input
Sample output