|Online Judge||Problem Set||Authors||Online Contests||User|
While Florida's difficulties electing presidents are well known, a lesser known problem is electing committee chairs within the state's House of Delegates. The process used is a runoff election,where each committee member submits a ballot with a ranked list of other members for the position of chair. Unfortunately, those responsible for tabulating the votes keep losing track of which ballots still have countable votes, and so no one trusts the results.
Each committee member submits a ballot. Each ballot contains a ranked list of votes. Tabulating the votes proceeds in rounds. For the first round, the first vote on each ballot is counted. If any candidate has more than half of the votes, they win.
After each round, the candidate receiving the fewest votes (or candidates, in the case of a tie for fewest votes) is eliminated. Votes are then re-tabulated with each ballot's highest vote for a remaining candidate being counted. If all of the candidates voted for on a ballot are eliminated,then that ballot is considered "non-viable," and it is no longer counted toward the total number of ballots when calculating majority.
The process is repeated until you have a single winner, or a tie between the remaining candidates.The rules of the election guarantee you will have a tie or a winner.
For each dataset:
Line 1 < candidates > < ballots >
The number of candidates receiving votes
The number of ballots, b
b Lines One line per ballot. For each ballot, the names of the candidates are listed in order of preference. A candidate name is a string with no whitespace in it. A ballot may not contain votes for all candidates. No candidate will be repeated on a single ballot.
After the last dataset, a line of
will indicate the end of the input.
For each dataset a single line is output:
For a winner:
< candidate > won
For a tie:
it is a tie between < candidate > and < candidate > [ and < candidate > [...]]
Each candidate name is separated by "and". They may be printed in increasing order.
3 9 Buchanan Bush Buchanan Bush Buchanan Gore Gore Bush Gore Bush Gore Bush Gore Bush Bush Buchanan Bush Buchanan 0 0
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator