Task 58. Формула 1
UniLecsЗадача: в формуле 1 изменилиись правила. Теперь перед тем как выехать команда может выполнить нектр модернизации болида.
Для каждой модернизации известно на сколько она увеличивает скорость болида, а также время за ктр она может быть выполнена.
Можно выполнить несколько различных модернизаций, но каждая модернизация может быть выполнена не более одного раза.
Дано расстояние трассы Dist (метры),
Скорость болида без модернизации - V (м/с)
Vi - Массив, i-й элемент массива содержит прирост скорости (м/с) после модернизации болида.
Ti - Массив, i-й элемент массива содержит время (сек) затрачиваемое на i-ю модернизацию из массива Vi
Вывести минимальное время, ктр потребуется пилоту для того, чтобы проехать трассу длиной l с учетом времени на всевозможные модернизации болида.
Например,
Dist = 100
V = 5
Vi = [ 5 5 ]
Ti = [ 3 3 ]
Вывод:
12.66
Идея: используем метод динамического программирования. Создадим массив deltaT, deltaT[i] будет хранить наименьшее время, через ктр можно добиться прибавки скорости i.
По умолчанию положим deltaT[i] = MAX_VALUE (большое число или бесконечность), deltaT[0] = 0.
Рассмотрим пару модернизации (vi, t), ктр означает, что за время t можно получить прирост скорости vi.
Также рассмотрим прирост скорсоти j, ктр можно получить за время deltaT[j].
Тогда получим, что используя модернизацию (vi, t) можно получить прирост скорости j + vi за время deltaT[j] + t.
И если это время окажется меньше deltaT[j + vi], то значение deltaT[j + vi] нужно улучшить.
Дальше нам нужно найти время, за ктр можно пройти всю трассу учитывая приросты скорости после модернизаций. Например, если болид будет ехать со скоростью v + i, то его время составит Dist/(v + i) + deltaT[i]. Среди всех таких значений времени находим наименьшее.
Рассмотрим как изменяется состояние массива deltaT с обработкой очередной модернизации.
Например deltaT[5] = 10 означает, что прирост скорости 5 можно набрать за 10 секунд. Для этого достаточно воспользоваться второй и третьей модернизациями.
Реализация:
https://gist.github.com/unilecs/cc9ada1226f3586fd6d8d51c31ae45e8
Тест: