Tribal Legislation
Time Limit: 1 Second Memory Limit: 32768 KB
The Zhombi tribe populates an island in the South Pacific. The tribe consists
of a number of clans (which are collections of related families). The tribe
has a chief, and so does each clan.
When a tribal law is proposed, the voting members of each clan convene and vote
on the proposal. In case of a tie, the clan chief (who is otherwise not a voting
member) will break the tie.
After the clans have voted, the clan chiefs convene at the tribal headquarters
to conduct the tribal level vote, which will determine whether the proposal
passes. There each clan chief will cast a number of votes equal to the number
of voting members of his/her tribe. Furthermore, all votes cast by one clan
chief will be either in favor of the proposal or against the proposal, depending
on how his/her clan voted. For example, if clan A has 28 voting members and
voted in favor of the proposal, then clan A's chief will cast all 28 votes in
favor of the proposal at the tribal level, even if the vote at the clan level
was "5 for 13 against" or if the vote at the clan level was a 14:14
tie that the clan chief chose to break in favor of the proposal.
In case of a tie at the tribal level vote, the tribal chief (who is otherwise
not a voting member) will break the tie.
You probably suspect now that a proposal could pass at the tribal level even
if fewer than 50% of all votes were cast in its favor at the clan level. The
main goal of the program will be to determine the smallest number of clan-level
votes needed to pass a law at the tribal level, without having to break a tie
either at the clan level or at the tribal level.
The input to your program will
contain at least two, but no more than 20 integers, all on one line, separated
by blank spaces, without any trailing blanks. Each of these numbers will be
in the range 2..999.
This problem contains multiple test cases!!
The first line of a multiple input is an integer N, then a blank line followed
by N input blocks. Each input block is in the format indicated in the problem
description. There is a blank line between input blocks.
Input
Each number in the input represents the number of voting members of a clan (not counting the chief). We will refer to the clans of the tribe by upper case letters, in alphabetical order. Thus, the data in this sample input specify that the tribe consists of four clans, A, B, C, and D, having 28, 12, 15, and 7 voting members, respectively.
Output
The output presents a scenario in which a proposal passes at the tribal level
with the smallest possible number of supporting votes at the clan level, without
having to break a tie either at the clan level or at the tribal level.
The line labeled "Clan" lists (in increasing alphabetical order) those
clans that voted in favor of the proposal.
The line labeled "Clan level votes" lists the (smallest) number of
clan-level votes needed from each clan that voted in favor of the proposal,
in order to pass the proposal at the tribal level. In those clans that are not
listed, all votes were cast against the proposal.
The line labeled "Tribal level votes" lists the votes cast in favor
of the proposal at the tribal level.
The two "summary" lines:
The number 19 represents the crux of the results, it is the smallest number
of clan-level votes which can result in the stated goal.
The total (62 in this case) will always be the same number on the two "summary"
lines; it is simply the sum of the numbers in the input.
The percentage of tribal-level votes (56.5% in this case) will always be greater
than 50%. (In some cases the output, rounded to one decimal place, may be 50.0%
even though the actual percentage is greater than 50%.)
Non-uniqueness of output
For the specific input shown above, the output shown above is not the only correct
output. Here is another instance of correct output for the input shown in the sample input:
Program 5 by team X Clan: B C D Clan level votes: 7 8 4 Tribal level votes: 12 15 7 Clan level summary: 19 out of 62, 30.6% Tribal level summary: 34 out of 62, 54.8% End of program 5 by team X
In particular, for a given input, all correct instances of output will be identical
on the line "Clan level summary". You will have to output the one with the
smallest value on "Tribal level summary". Break further ties with the lexicographic
order of the tribes involved considering it as a character string. Thus the second
sample output is the desired result by this definition.
Pay attention to all formatting details, such as the presence or absence of
blanks lines, blank spaces, punctuation, upper/lower case letters.
The letters and numbers displayed on the "Clan", "Clan level
votes" and "Tribal level votes" lines
are right-justified in fields of width 4.
Integer values that appear in the "summary" lines are right-justified
in fields of width 6.
You may assume that no more than 14 clans voted in favor of the proposal.
Here is a formatting template shown between two lines of the second instance
of output from sample output:
Tribal level votes: 12 15 7 12345678901234567890123456789012345678901234567890 Clan level summary: 19 out of 62, 30.6%
Note the column numbers of the '9' in 19, the comma, the decimal point, and
the percent sign.
The percentages are displayed to a precision of one digit after the decimal
point.
The output format consists of N output blocks. There is a blank line between output blocks.
Sample Input
28 12 15 7
Sample Output
Program 5 by team X Clan: A D Clan level votes: 15 4 Tribal level votes: 28 7 Clan level summary: 19 out of 62, 30.6% Tribal level summary: 35 out of 62, 56.5% End of program 5 by team XSubmit
Source: Rocky Mountain 2000