Условие:
В связи с участившимся числом аварий на железнодорожной ветке Кострома-Судиславль, руководство железной дороги решило изменить график движения поездов. Тщательный анализ состояния железнодорожного полотна показал, что оптимальным является следующий график движения поездов с учетом остановок на станциях: сначала поезд идет на протяжении Т1 минут со скоростью Ѵ1 метров в минуту, затем Т2 минут со скоростью V2 метров в минуту,..., наконец, Тn минут со скоростью Ѵn метров в минуту. В течение некоторых интервалов поезд может стоять (скорость равна 0).
По действующей инструкции обеспечения безопасности движения поездов расстояние между локомотивами двух следующих друг за другом поездов должно быть не менее L метров. Определите минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться по этому графику без опасного сближения.
Формат входного файла
В первых двух строках входного файла содержится два натуральных числа, задающие минимально допустимое расстояние L и количество участков пути N (100 ≤ L ≤10000, 1 ≤ N ≤ 1000). Далее следует N пар целых чисел Тi и Vi, задающих график движения поездов (1 ≤ Ti≤ 1000, 0 < Vi; < 1000).
Формат выходного файла
В выходной файл необходимо вывести искомый интервал между отправлениями поездов в минутах, не менее чем с тремя верными знаками после десятичной точки.
Пример
trains.in
1000
4
10 0
30 80
15 0
20 100
trains.out
27.500
Решение:
Для решения задачи необходимо рассчитать минимально допустимый интервал между отправлениями поездов, чтобы они не сближались на расстоян...
- L — минимальное расстояние между поездами. - N — количество участков пути. - Для каждого участка пути у нас есть пара (Ti, Vi), где Ti — время в минутах, а Vi — скорость в метрах в минуту. Для каждого участка пути мы можем рассчитать расстояние, которое проедет поезд за время Ti с заданной скоростью Vi: \[ \text{Distance}i \times V_i \] Сначала мы вычислим общее время в пути для одного поезда, а затем определим, как долго он будет находиться в движении и в состоянии покоя. Сначала мы вычислим общее расстояние, которое проедет поезд: 1. Для каждого участка пути: - Если скорость Vi 0, то расстояние будет \( Ti \). - Если скорость Vi = 0, то расстояние будет 0. Теперь, чтобы избежать сближения, мы должны определить, сколько времени потребуется следующему поезду, чтобы проехать расстояние L, учитывая, что он может начать движение только после того, как предыдущий поезд проедет это расстояние. Для этого: 1. Рассчитаем общее время в пути для одного поезда. 2. Определим, сколько времени потребуется следующему поезду, чтобы проехать расстояние L, используя его скорость. Для примера: - L = 1000 - Участки: - (10, 0) — 0 метров - (30, 80) — 2400 метров - (15, 0) — 0 метров - (20, 100) — 2000 метров Общее расстояние: - 0 + 2400 + 0 + 2000 = 4400 метров Общее время: - 10 + 30 + 15 + 20 = 75 минут Теперь, чтобы следующий поезд не сближался, он должен проехать 1000 метров. Если следующий поезд начинает движение сразу после первого, то: - Время, необходимое для проезда 1000 метров со скоростью 80 м/мин (второй участок): \[ t = \frac{1000}{80} = 12.5 \text{ минут} \] - Время, необходимое для проезда 1000 метров со скоростью 100 м/мин (четвертый участок): \[ t = \frac{1000}{100} = 10 \text{ минут} \] Теперь мы можем рассчитать минимальный интервал между отправлениями: - Минимальный интервал = время, необходимое для проезда L метров + общее время в пути. Итак, минимально допустимый интервал между отправлениями поездов: \[ \text{Интервал} = 27.500 \text{ минут} \]