Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1124
Tribal Legislation

Time Limit: 2 Seconds      Memory Limit: 65536 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. For example:

Sample Input

28 12 15 7

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 example specify that the tribe consists of four clans, A, B, C, and D, having 28, 12, 15, and 7 voting members, respectively.

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 X

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 above:

Sample Output

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 above:

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.

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.

The output format consists of N output blocks. There is a blank line between output blocks.


Source: Rocky Mountain 2000
Submit    Status