- Описание
- Отправленные решения
281. Парикмахерская
Николай работает в парикмахерской в большом городе. В один день Николай перед походом на работу понял, что не сможет обслужить всех своих записанных $N$ клиентов на день, а сможет обслужить только $K$. Поскольку Николай не сможет приехать на работу дважды и делать перерыв, ему необходимо, чтобы $K$ клиентов шли подряд. Зная вероятности, что клиент больше никогда не вернётся в парикмахерскую при отмене, необходимо найти минимальное математическое ожидание числа потерянных клиентов при наилучшем варианте отмене стрижек.
Формат ввода
В первой строке идёт число $N$ ( $1 \le N \le 1000000$). Во второй строке число $K$ ( $0 \le K \le N$). Далее идут $N$ строк с дробным числом от 0 до 1. $i$-ое число означает вероятность, что $i$-ый клиент не вернётся после отмены стрижки.
Формат вывода
Дробное число — минимальное математическое ожидание числа потерянных клиентов.
Ограничения
Ограничение времени
10 с
Ограничение памяти
256 МБ
Пример 1
5
3
0.668103249992
0.525906286805
0.0793836313371
0.986652106472
0.010960416731
0.679063666723