eolymp
bolt
Try our new interface for solving problems
Məsələlər

Игровые реликвии

Игровые реликвии

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Киберспорт - это форма соревновательного спорта с использованием видеоигр. Dota 2 - одна из самых популярных соревновательных видеоигр в киберспорте. Недавно вышла новая видеоигра Dota 3. В Dota 3 игрок может купить реликвии для своего героя. Реликвии - это счетчики, которые отслеживают действия и статистику героя в игре.

Глории нравится играть в Dota 3, поэтому она хочет купить все n доступных реликвий для своего любимого героя.

Реликвии можно купить за внутриигровую валюту, называемую осколками. Каждая реликвия имеет свою цену - c[i] осколков за i-ю реликвию. Игрок может купить реликвию одним из следующих способов:

  • Заплатить c[i] осколков, чтобы купить i-ю реликвию;

  • Заплатить x осколков и случайным образом получить одну из всех имеющихся n реликвий. Вероятность получения реликвии одинакова для всех n реликвий. Если получен дубликат реликвии, то реликвия перерабатывается, и игроку возвращается x / 2 осколков.

Глория хочет купить все n реликвий. Помогите ей минимизировать ожидаемое количество осколков, которое она потратит на покупку всех реликвий.

Giriş verilənləri

Первая строка содержит два целых числа n и x (1n100, 1x10000) - количество реликвий и стоимость получения случайной реликвии.

Вторая строка состоит из n целых чисел c[1], c[2], ..., c[n] (xc[i]10000, Σ c[i]10000) - цены на n реликвий.

Çıxış verilənləri

Выведите одно действительное число - минимальное ожидаемое количество осколков, которое Глория должна потратить чтобы купить все реликвии. Абсолютная или относительная ошибка не должна превышать 10^(-9).

Nümunə

Giriş verilənləri #1
2 20
25 100
Çıxış verilənləri #1
47.50000000000000000
Giriş verilənləri #2
4 30
60 50 60 80
Çıxış verilənləri #2
171.25000000000000000

Qeyd

В первом примере оптимальная стратегия - случайным образом получить одну из двух реликвий, заплатив 20 осколков. Далее имеются два сценария.

Первый сценарий произойдет, если Глория получит первую реликвию. Затем она продолжит получать случайные реликвии, пока не получит вторую реликвию. Ожидаемое количество осколков, которое следует потратить в этом сценарии, составит 20 + 30 = 50.

Во втором сценарии Глория изначально получает вторую реликвию. Тогда лучше купить первую реликвию за 25 осколков, поэтому ожидаемое количество осколков, которое нужно потратить в этом сценарии, составляет 20 + 25 = 45. Таким образом, ожидаемое количество осколков, которые нужно потратить, составляет (50 + 45) / 2 = 47:5.

Mənbə 2019 ACM NEERC, Полуфинал, Декабрь 1, Задача G