Давление пива
С середины 20-го века социологи изучают интересное явление — поведение студентов в Делфте, связанное с выбором паба. Одним из значительных достижений стало создание точной модели, описывающей сложный ритуал выбора паба, который происходит после занятий.
Студенты выбирают паб путем голосования. Интерес социологов вызывает сочетание доминирующего поведения некоторых студентов и поведения, обусловленного давлением со стороны сверстников, с элементом случайности у других студентов.
Конкретно, модель, описывающая ритуал выбора паба, выглядит следующим образом:
Доминирующие студенты, имеющие сильное предпочтение к определенному пабу, (громко) объявляют о своем голосе. Несколько доминирующих студентов могут проголосовать за один и тот же паб.
Затем оставшиеся студенты голосуют по одному. Эти недоминирующие студенты голосуют вероятностно и подвержены давлению со стороны сверстников; вероятность того, что они проголосуют за конкретный паб, равна количеству голосов, отданных за этот паб на данный момент, деленному на общее количество голосов, отданных на данный момент.
В конце, когда все голоса подсчитаны, паб с наибольшим количеством голосов выбирается. Если несколько пабов получили одинаковое наибольшее количество голосов, один из них выбирается случайным образом с равной вероятностью.
Например, в одном случае с семью студентами, пять доминирующих студентов начинают с объявления своих голосов за три разных паба. Три доминирующих студента заявляют о предпочтении первого паба; четвертый доминирующий студент объявляет о своем предпочтении второго паба, и последний доминирующий студент голосует за третий паб. Это оставляет начальное количество голосов равным (3, 1, 1).
После этого оставшиеся два недоминирующих студента начинают голосовать, один за другим. Первый из них выберет либо паб номер один с вероятностью 3/5, паб номер два с вероятностью 1/5, либо паб номер три с вероятностью 1/5. Он случайно выбирает паб номер три, и количество голосов становится (3, 1, 2).
Наконец, последний студент выберет либо паб номер один с вероятностью 1/2, паб номер два с вероятностью 1/6, либо паб номер три с вероятностью 1/3. Она также выбирает паб номер три.
Это оставляет окончательное количество голосов равным (3, 1, 3): ничья между первым и третьим пабами. Эта ничья разрешается подбрасыванием монеты; с вероятностью 1/2 выбирается первый паб для вечернего распития.
Задача
Вы — социолог, наблюдающий описанный выше ритуал. После того, как доминирующие студенты закончат объявлять свои голоса, вы хотите узнать, каковы вероятности для каждого паба, что именно он будет обслуживать студентов в ту ночь.
Входные данные
Для каждого теста входные данные состоят из двух строк:
строка, содержащая два положительных целых числа: n, обозначающее количество пабов в этом испытании (n ≤ 5); и k, общее количество студентов, как доминирующих, так и недоминирующих (k ≤ 50).
строка, содержащая n положительных целых чисел (α_1, α_2, ..., α_n), обозначающих количество голосов сразу после того, как все доминирующие студенты проголосовали.
Кроме того, гарантируется, что .
Выходные данные
Для каждого теста напишите n строк вывода, содержащих вероятность того, что i-й паб будет выбран (1 ≤ i ≤ n), упорядоченных по возрастанию i.
Каждая строка должна быть в формате 'pub i: percentage %', где percentage — это число с плавающей запятой, округленное до 2 знаков после запятой.
Пробел должен отделять число процентов и последующий знак процента.