Not an official ACM page
[Problem B | 1993 East-Central Regional problem set | My ACM problem archive | my home page]

1993 East-Central Regionals of the ACM International Collegiate Programming Contest

Problem A

Transferable Voting

In Fredonia, elections are conducted using a transferable vote system. When they enter the polling booth, Fredonians are presented with a list of candidates like
  1. Tammy Fay Bakker
  2. Jimmy Hoffa
  3. Al Capone
  4. Bonnie Parker
  5. Elmer Fudd
A vote is cast by typing the numbers of the candidates in the preferred order. Thus a Fredonian who likes Jimmy Ho a best, with Elmer Fudd second, but who does not care about the other three candidates, would type:
2 5
Each integer corresponds to the number preceding a valid candidate on the list. No number should appear more than once on a single ballot. Ballots which do not meet these rules are called spoiled ballots. Unspoiled ballots are called valid ballots. Your program should count these spoiled ballots. The outcome of the election should be the same as if the spoiled ballots had never been cast. When polling is complete, the outcome of the election is calculated as follows. First, all the first-preference votes (on valid ballots) are counted. After this count, if the number of votes for any candidate is more than half of the number of valid ballots, that candidate is declared the winner. Otherwise, the candidate(s) with the fewest number of votes is (are) eliminated. Ballot papers on which an eliminated candidate is mentioned are e ectively modified by deleting that candidate, thereby "promoting" any lower-preference non-eliminated candidates. (A valid ballot from which all candidates have been eliminated remains a valid ballot.) If, after the elimination, there are any remaining candidates, the first-preference votes are counted again to determine a winner. If, after the elimination, no candidates are left, the election is declared indecisive. You are to write a program to calculate the outcome of Fredonian elections.

The input consists of a list of candidates and a list of ballots separated by a blank line (a newline by itself on an otherwise empty line). The list of candidates is an ordered list of up to 20 candidates, one per line. Each candidate's name can be up to 20 characters long. The first candidate's name will be preceded by the string "1. ", the second by "2. ", etc. The list of ballots consists of at most 1000 ballots. There are no blank ballots: each ballot has at least one integer. Each ballot consists of a sequence of integers, which are separated by single spaces, and is terminated by a newline. The list of ballots is terminated by an end-of-file.

Your program should produce the following output. As each candidate is eliminated, a message to that e ect must be printed. If more than one candidate is eliminated in the same round (because they each had the minimum number of first-preference votes at that stage) then their eliminations should be output in the order in which the candidates originally were input. An elimination is recorded like this:

John Minor with 3 votes is eliminated.
Next your program should either declare the winner, like
The winner of the election is Clint Eastwood.
or declare that the election was indecisive by printing
The election was indecisive.
Finally, you should print a count of the valid ballots and the spoiled ballots. For example,
There were 457 valid ballots and 3 spoiled ballots.
After this last line there should be no blank line. The next two pages each contain a sample input and corresponding output.

Sample Input 1

1. Betty Boop
2. Elmer Fudd
3. Olive Oyl

1 2 3
1 2 3
1 2 3
2 1 3
2 1 3
2 1 3
3 1 2
3 1 2
3 1 2

Sample Output 1

Betty Boop with 3 votes is eliminated.
Elmer Fudd with 3 votes is eliminated.
Olive Oyl with 3 votes is eliminated.
The election was indecisive.
There were 9 valid ballots and 0 spoiled ballots.

Sample Input 1

1. Bill Clinton
2. Barbara Bush
3. Margaret Thatcher
4. John Minor
5. Clint Eastwood
6. Jesse Ventura
7. Sonny Bono
8. Cher

2 4 6 8
1 2 3
5 7
8
6 6
5
5
5
5 7 2
8
3 2 5

Sample Output 1

John Minor with 0 votes is eliminated.
Jesse Ventura with 0 votes is eliminated.
Sonny Bono with 0 votes is eliminated.
Bill Clinton with 1 votes is eliminated.
Barbara Bush with 1 votes is eliminated.
Margaret Thatcher with 1 votes is eliminated.
The winner of the election is Clint Eastwood.
There were 10 valid ballots and 1 spoiled ballots.

This page maintained by Ed Karrels.
Last updated November 6, 1997