Tickets
TopCoder TCO2017 Round 1C
Time Limit: 0.1s, Memory Limit: 64MiB
Всеки ден Ели пътува с метрото от къщи до центъра на града. По пътя ѝ има N+1 станции, номерирани от 1 до N+1 в реда, в който влакът ги посещава. Ели се качва на станция 1 и слиза на станция N+1.

Цената на билетите в общественият транспорт в града, където живее Ели, зависи от това колко близо до последната станция човек си купи билет – колкото по-близо, толкова по-малко трябва да заплати. Билет може да бъде закупен от всяка станция докато влакът е спрял там. Цената на билет, закупен от станция i, е Pi лева.

Пътниците не са задължени да купят билет на станцията, на която се качват. Нещо повече, те могат да не си купят билет въобще! Ако бъдат хванати без билет, обаче, те трябва да заплатят глоба от M лева. След заплащането ѝ, те могат да продължат пътуването си без да купуват билет.

Ели е установила, че нейният влак бива проверяван от един единствен контрольор. Всеки ден той се качва на някоя станция i, проверява всички пътници, и слиза на станция i+1. Контрольорът избира числото i на случаен принцип от множеството {1, 2, …, N}. С други думи, контрольорът си избира една от N-те отсечки между двойка съседни спирки, в която проверява всички билети. Забележете, че ако Ели си купи билет на станцията, на която се качи контрольорът, тя няма да бъде глобена, тъй като ще има валиден билет, когато бива проверена.

Ели иска да даде възможно най-малко пари за нейното пътуване. Сега тя се чуди каква е очакваната сума, която ще заплати, при оптимален избор къде (и дали) да си купи билет.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя спирки, на които може да се качи контрольорът, и цената на глобата. На следващия ред ще са зададени N не-увеличаващи се цели числа P1, P2, …, PN – цената на билета на всяка от станциите.
Изход
На стандартния изход изведете едно число с плаваща запетая – очакваната цена за пътуването на Ели. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ M ≤ 1,000
  • 1 ≤ PNPN-1 ≤ … ≤ P1 ≤ 1,000
Примерен Вход Примерен Изход
3 10 8 5 3 6.6666666666
5 42 50 40 30 20 10 33.2
11 100 97 97 85 72 66 66 55 42 17 13 11 77.363636364
В първия пример една възможна стратегия би била Ели да си купи билет още на първата станция. Билетът там струва 8 лева, и тъй като така е гарантирано, че няма да я глобят, очакваната сума, която ще заплати, е точно толкова.
Съществува, обаче, по-добра стратегия. Ели може да се вози без билет за една спирка, закупувайки си такъв чак на втората станция. Така тя има шанс 1/3 да бъде глобена – ако контрольорът се качи на първата станция – в който случай тя ще трябва да заплати глобата от 10 лева. Ако контрольорът се качи на някоя от другите станции, обаче, тя ще заплати само 5 лева за пътуването си - цената на билета от втората станция. Така очакваната сума за пътуването е 1/3 * 10 + 2/3 * 5 = 20/3 = 6.66(6) лева.
Мрън!