ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2012, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Руины титанов: наперегонки с огнём

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В очередной раз Сорен обошёл комнату в поисках потайных дверей, но не нашёл их.
— Кажется, нам всё же придётся спуститься по этому тоннелю.
— Ему же конца не видно…  — вздохнул Альба.
— О! У меня есть идея. Видишь, там тележка стоит? Давай на ней скатимся, так быстрее выйдет.
Друзья сели в тележку и покатились вдоль тоннеля. К их счастью, пол в тоннеле был ровный, сам тоннель нигде не сужался, и потому тележка ехала хоть и почти впритык к стенам, но уверенно и достаточно быстро.
Через несколько минут Сорен обратил внимание на какой-то шум позади. Обернувшись, он увидел большую проблему — их стремительно нагоняла стена огня. Похоже, что они случайно активировали очередную ловушку.
— Слушай, если мы ничего не сделаем, этот огонь нас догонит и сожжёт.
— Я, конечно, могу выставить силовое поле вокруг нас, которое будет удерживать стену огня впритык за тележкой. Но на это уйдёт много сил, а конца тоннелю всё ещё не видно.
— Ты маг или нет? Воспользуйся заклинанием сканирования пространства!
— Хм, и правда… Так, впереди есть несколько ответвлений. Каждое из них сначала отходит от тоннеля, а затем вновь в него вливается. Значит, мы можем свернуть в одно из них, чтобы стена огня, двигаясь по основному тоннелю, нас обогнала. Там, правда, пол не такой ровный и тележка явно будет замедляться, но это скорее плюс — было бы неприятно вернуться в тоннель до того, как стена огня целиком уйдёт вперёд нас.
— Хорошо, что ты подумал об этом… Вполне возможно, что в ответвлении нам придётся применить заклинание, дополнительно замедляющее тележку на протяжении этого ответвления. И даже если тележка полностью остановится и придётся дальше идти пешком — это всё равно лучше, чем сгореть здесь.
Стена огня всё приближается и времени на раздумья осталось совсем немного — друзьям срочно надо выбрать какое-то одно ответвление для манёвров, рассчитать заклинания и спасаться!
Пока тележка едет по основному туннелю, она едет с постоянной скоростью. Но как только тележка целиком окажется в ответвлении, она начнёт равномерно замедляться из-за того, что пол там менее ровный. Замедление во всех ответвлениях одинаковое, но с помощью специального заклинания можно увеличить замедление в любом из ответвлений. На это заклинание можно потратить любое количество энергии, и результат (то, насколько увеличится замедление) будет пропорционален количеству потраченной энергии. Силовое поле можно использовать, когда огонь подошёл к тележке вплотную. Поле будет сдерживать наступление стены огня, но на поддержание силового поля приходится постоянно расходовать магическую энергию. Разумеется, как только тележка окажется вся в ответвлении, необходимость в силовом поле пропадёт.

Исходные данные

В первой строке через пробел заданы целые числа v — скорость тележки, l — длина тележки, V — скорость стены огня, когда её не удерживает силовое поле, L — толщина стены огня, D — текущее расстояние от переднего края стены огня до заднего края тележки, a — замедление тележки в ответвлении, обусловленное неровностью пола, k — расход магической энергии в секунду на поддержание силового поля за тележкой, s — удельное количество магической энергии, необходимое для создания единицы дополнительного замедления на протяжении всего ответвления (0 < v, V, a, l, L, D < 105; v < V; 0 ≤ k, s ≤ 104).
Во второй строке дано число n — количество ответвлений (1 ≤ n ≤ 1 000). В следующих n строках дано по два целых числа li, ri — расстояния до начала и до конца очередного ответвления от переднего края тележки (0 < li; li + l < ri < li+1; ri < 105).
Все длины даны в метрах, скорости — в метрах в секунду, a — в единицах ускорения — единицах скорости в секунду, k — в единицах магической энергии в секунду, s — в единицах магической энергии на единицу ускорения.

Результат

Выведите единственное число — минимальное количество магической энергии, которое нужно потратить, чтобы пропустить стену огня вперёд. С абсолютной или относительной погрешностью не более 10−5.

Пример

исходные данныерезультат
1 1 2 1 1 100 1 1234
1
100 102
100.000
Автор задачи: Денис Дублённых
Источник задачи: NEERC 2012, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1911. Руины титанов: наперегонки с огнём