B :: Beer Pressure

Time Limit: 3 Seconds Memory Limit: 65536 KB

Ever since the middle of the 20th century, sociologists have been studying the fascinating topic of beer-related behaviour among the student population in Delft. One of the great successes has been the development of a highly accurate model that describes the intricate ritual of pub selection, that can be observed in the afternoon after the courses for the day are done.

Students select a pub by casting votes. What makes it interesting from a sociological perspective is the mix of dominant behaviour by some students, and behaviour driven by peer pressure combined with randomness by other students.

Specifically, the model used to describe the pub selection ritual is this:

• The dominant students, who have a strong preference for a particular pub, will (loudly) announce their vote. Several dominant students may vote for the same pub.

• Next, the remaining students vote, one by one. These non-dominant students vote probabilistically and are subject to peer pressure; the probability that they will vote for any specific pub is equal to the number of votes cast for that specific pub so far, divided by the total number of votes cast so far.

• Finally, when all votes are in, the pub with the highest number of votes is selected. If several pubs received the same highest number of votes, one of those is selected at random, with equal probability.

For example, in one particular instance with seven students, the five dominant students start by declaring their votes for three different pubs. Three dominant students proclaim a preference for the first pub; the fourth dominant student announces her preference for a second pub, and the last dominant student votes for the third pub. This leaves the initial vote-count at (3, 1, 1).

After that, the remaining two non-dominant students start to vote, one after the other. The first of them will pick either pub number one with probability 3/5, pub number two with probability 1/5 , or pub number three with probability 1/5. He happens to pick pub number three, and the vote-count becomes (3, 1, 2).

Finally, the last student will pick either pub number one with probability 1/2 , pub number two with probability 1/6 , or pub number three with probability 1/3 . She, too, picks pub number three.

This leaves the final vote-count at (3, 1, 3): a tie between pub one and pub three. This tie is broken by a coin-toss; with probability 1/2 , pub one is selected for that evening’s drinking.

You are a sociologist observing the ritual described above. After the dominant students are done declaring their votes, you want to know what the probabilities are for each pub that they will be serving drinks to the students that night.

Input

For each test case, the input consists of two lines:

• a line containing two positive integers: n, denoting the number of pubs in this trial (n ≤ 5); and k, the total number of students, both dominant and non-dominant (k ≤ 50).

• a line containing n positive integers (α₁ , α₂ , . . . , α_n ), denoting the vote-count right after all dominant students have cast their vote.

Furthermore, it is guaranteed that k ≥ α₁ + α₂ + . . . + α_n

Output

For each test case, write n lines of output containing the probability that the i’th pub will be selected (1 ≤ i ≤ n), ordered by ascending i.

Each line shall be of the form ‘pub i: percentage %’, where percentage is a floating point number rounded to 2 digits after the decimal point.

A space should separate the percentage number and the subsequent percent sign.

Sample Input

3 7 
3 1 1

Sample Output

pub 1: 93.33 %
pub 2: 3.33 %
pub 3: 3.33 %

Submit

Source: NWERC 2012