ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрФУ 2014

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Тысяча чертят

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Саша любит сказочные миры и истории про драконов, спасающих принцев от ужасных принцесс, поэтому он постоянно ходит в кино на мультфильмы.
Проблема в том, что на такие сеансы всегда приходит куча детей. Если заранее занять своё место, то каждый проходящий мимо тебя ребёнок может облить тебя колой. А если зайти в зал самым последним, то каждый ребёнок, мимо которого ты будешь протискиваться к своему месту, будет норовить пнуть тебя. Поэтому в последнее время Саша, заходя в зал, смотрит, какие места уже заняты, и в зависимости от этого принимает решение: ждать в проходе или идти к своему месту.
Саша знает, что
  • если в момент, когда он заходит в зал, какое-то место ещё свободно, то с вероятностью p% до начала сеанса его никто так и не займёт;
  • зрители заходят в зал по одному и в совершенно случайном порядке;
  • все зрители, в том числе и Саша, проходят к своему месту с левого края ряда;
  • опоздавших зрителей в зал не пускают. Поэтому если в момент начала сеанса Саша всё ещё стоит в проходе, то он понимает, что пропускать больше никого не придётся и садится на своё место.
Учитывая всё это и видя, какие места в его ряду уже заняты, Саша хочет выработать стратегию, которая минимизировала бы сумму количества зрителей, через которых он пройдёт к своему месту, и количества зрителей, которые пройдут к своему месту через него. Определите, чему равняется матожидание искомой суммы при оптимальной стратегии.

Исходные данные

В первой строке даны целые числа n и p — количество мест в ряду и вероятность в процентах, что свободное место до начала сеанса никто не займёт (1 ≤ n ≤ 1 000; 0 ≤ p ≤ 100). Во второй строке записаны n символов, описывающих занятые места в ряду в тот момент, когда Саша заходит в зал. i-й символ равен 0, если i-е слева место свободно, 1, если оно занято, и 2, если это место Саши. Гарантируется, что в строке есть ровно один символ 2.

Результат

Выведите искомое матожидание с абсолютной или относительной погрешностью не более 10−6.

Примеры

исходные данныерезультат
5 0
01120
2.500
3 50
020
0.375

Замечания

В первом примере оптимальная стратегия — ждать, пока не сядет пятый зритель (считая слева), и занимать своё место сразу после этого. Если пятый зритель придёт раньше первого, то Саше придётся пройти через двух зрителей, если позже — через трёх зрителей. Вероятность каждого из этих событий составляет 0.5, поэтому искомое матожидание равняется 0.5 · (2 + 3) = 2.5.
Во втором примере нужно ждать, пока не придёт третий зритель или не начнётся сеанс. С вероятностью 0.375 следующим в зал зайдёт первый зритель (и Саше придётся пройти через него), с вероятностью 0.375 — третий зритель, и с вероятностью 0.25 никто из них не придёт до начала сеанса.
Автор задачи: Денис Дублённых
Источник задачи: Открытое личное первенство УрФУ по программированию 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2094. Тысяча чертят