시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 45 | 15 | 11 | 32.353% |
The following is from Ballotpedia [ https://ballotpedia.org/Ranked-choice_voting_(RCV) ]:
Broadly speaking, the ranked-choice voting process unfolds as follows for single-winner elections:
Example: Assume that there are four candidates in an election. The table below presents the raw first-preference vote totals for each candidate:
Raw first-preference vote tallies | ||
---|---|---|
Candidate | First-Preference Votes | Percentage |
Candidate A | 475 | 46.34% |
Candidate B | 300 | 29.27% |
Candidate C | 175 | 17.07% |
Candidate D | 75 | 7.32% |
In the above scenario, no candidate won an outright majority of first-preference votes. As a result, the candidate (Candidate D) with the smallest number of first-preference votes is eliminated. The ballots that listed candidate D as the first preference are adjusted, raising their second-preference candidates. Assume that, of the 75 first-preference votes for Candidate D, 50 listed Candidate A as their second preference and 25 listed Candidate B. The adjusted vote totals would be as follows:
Adjusted vote tallies | ||
---|---|---|
Candidate | Adjusted First-Preference Votes | Percentage |
Candidate A | 525 | 51.22% |
Candidate B | 325 | 31.71% |
Candidate C | 175 | 17.07% |
On the second tally, Candidate A secured 51.22 percent of the vote, thereby winning the election.
Note: If several candidates are tied for the fewest first-preference votes, all such candidates are eliminated. So, candidates not eliminated must have at least one more first-preference vote than those eliminated.
We have received information on the percentage for the first-preference for each candidate, but we don’t know how the candidates are listed as the second preference, third preference, etc. Help write a program to remove candidates that cannot possibly win. More specifically, given the current votes for a set of candidates, find the set of candidates that cannot possibly win.
The first input line contains a single integer, N (1 ≤ N ≤ 100,000), representing the number of votes. Each of the following N input lines contains a candidate name receiving the first-place vote from that voter. Each candidate name is 1-25 letters (lowercase and uppercase), starting in column one.
On the first output line, print a single positive integer, C, the number of candidates that cannot win. Each of the remaining C output lines should contain a candidate name that cannot win. The candidate names should be printed in lexicographical order (increasing order).
5 Alice Alice Bob Bob Carol
1 Carol
2 Alice Bob
2 Alice Bob