Трамваи в Барселоне
Недавно в Барселоне трамвай включили в "эффективную" транспортную систему города. Как и ожидалось, результатом такого решения стало появление поломок, отличавшихся оригинальностью и красотой. Но не смотря на такую эстетику, мер Барселоны решил уменьшить время заторов, которые возникали в результате аварий. После скрупулезного изучения проблемы, он огласил следующую модель движения:
Каждый трамвай должен проехать с начальной станции P_0 до конечной P_n, посетив промежуточные станции P_1, ..., P_{n-1} именно в таком порядке. Для каждого 1 ≤ i ≤ n, пусть S_i - длина пути (секции) от P_{i-1} до P_i. Каждая такая секция должна быть пройдена с постоянной скоростью v_i, которая выбирается водителем на станции P_{i-1}. Пусть M_i - максимальная возможная скорость трамвая на участке S_i, и пусть выбранная на нем скорость равна 0 < v_i ≤ M_i. Вероятность поломки на участке S_i равна v_i/M_i. В случае аварии у трамвая включается система восстановления, на что уходит всего 10 секунд. Затем трамвай едет до P_i, используя дополнительный (медленный, но безопасный) двигатель, со скоростью 5 метров в секунду, и уже без поломок на S_i.
Например, пусть длина секции равна 300 метров, а максимально возможная скорость на этом участке равна 25 метров в секунду. Если водитель выберет скорость 25 м/с, то трамвай однозначно сломается. Так как авария может произойти где угодно между P_{i-1} и P_i, то для удобства будем считать что она произойдет как раз в середине пути (после 150 метров). Таким образом, трамвай проедет 6 секунд до середины пути, 10 секунд постоит пока будет включаться дополнительный двигатель после поломки, и за 30 секунд он достигнет P_i, всего таким образом потратив на путь 46 секунд. Если начальная скорость трамвая будет 15 м/с, то с вероятностью 0.6 он сломается и доедет за 10 + 10 + 30 = 50 секунд, и с вероятностью 0.4 достигнет P_i через 20 секунд без поломки. Среднее время проезда в этом случае составит 0.6·50 + 0.4·20 = 38 секунд.
Когда трамвай достигает P_i, он останавливается на несколько секунд независимо от того была авария на S_i или нет; этих нескольких секунд (для простоты вычислений будем считать их равными 0) достаточно чтобы полностью отремонтировать трамвай: максимальная возможная скорость уменьшается на 1 м/с после каждой поломки. Если начальная возможная максимальная скорость равна M_0, то M_i = M_0 - C_i, где 0 ≤ C_i ≤ i-1 общее количество аварий на участках S_1, ..., S_{i-1}.
Напишите программу, которая выведет наименьшее среднее время путешествия, если известна начальная максимальная допустимая скорость движения трамвая и длина каждой секции.
Входные данные
Каждая строка соответствует одному тесту и содержит начальную максимально возможную скорость трамвая M_0 (действительное число между 5 и 25), значение n (целое число между 1 и M_0 - 1), и длины всех секций (действительное число от 100 до 1000).
Выходные данные
Для каждого теста в отдельной строке вывести минимальное среднее время, за которое трамвай преодолеет весь путь. Ответ следует выводить с четырьмя десятичными знаками.