Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Широкие поля

Задачу добавил: alef

Успешно сдано решений: 31

Средний сын не стал обозов снаряжать - взял с собой только ларчик с украшениями, сел на коня быстрого и поскакал через широкие поля за своей суженой. Одна незадача - поля разные, по одним конь летит, словно птица, а по другим бредет еле-еле. Как же ему быстрее добраться?

По заданной «карте» полей необходимо построить маршрут, требующий наименьших затрат по времени. Карта состоит из полос разной ширины - полей. Для каждого поля определен «коэффициент проходимости» kj, который изменяет «базовую» скорость всадника в kj раз. Считается, что всадник выезжает из точки с координатами (0,0).

Формат входного файла input.txt

Первая строка - вещественное число X и целые числа T и V через пробел.

X (1<=X<=10000) - координата точки, в которую должен добраться всадник.

T (1<=T<=10) - количество полей на карте

V (1<=V<=100) - «базовая» скорость всадника

Вторая строка содержит T вещественных чисел k1, k2, …, kT через пробел - коэффициенты проходимости для каждого поля (0.01 <= kj <= 10, j = 1, 2, …, T).

Третья строка содержит T вещественных чисел s1, s2, …, sT через пробел - ширины каждого из полей (sj >= 0.001, j = 1, 2, …, T; s1 + s2 + s3 + … + sT <= 10000).

Примечание. Координата Y определяется следующим образом: Y = s1 + s2 + s3 + … + sT.

Формат выходного файла output.txt

Первая строка - вещественное число с точностью два знака после запятой - минимально возможное время, за которое всадник может добраться до точки с координатами (X, Y).

Пример входного файла

100 1 10

0.92

100

Пример выходного файла.

15.37


Сдать задачу

Задать вопрос жюри по этой задаче