Реши. Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось,

6 ноября 2025
Теоретическая механика

Условие:

Реши.
Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени, и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.

Черепаха может ползти со скоростью, не превосходящей величины vmax. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.

Требуется определить, в какой момент времени черепаха сможет вернуться домой, съев все одуванчики и затратив на путешествие наименьшее время.

Входные данные
В 1-й строке входного файла находятся 2 целых числа, разделенные пробелом: vmax (в см/мин) и d (в минутах), 0 < vmax ≤ 200, 0 ≤ d ≤ 500.

Во 2-й строке находится число N – количество одуванчиков (в штуках). 0 ≤ N ≤ 1400 при d = 0, в противном случае 0 ≤ N ≤ 200.

В каждой из последующих N строк расположены: целое число xi – расстояние от одуванчика до начала грядки (в сантиметрах), 0 ≤ xi ≤ 32767, и через пробел ti – момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выходной файл должен содержать момент времени возвращения черепахи домой (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания

1. В часе – 60 минут, в сутках – 24 часа.

2. Время в сутках изменяется от 00:00 до 23:59.

3. Можете считать, что черепаха не меняет направления движения до тех пор, пока не доползет до последнего одуванчика.

Примеры
Входные данные
3 1
1
100 00:01
Выходные данные
01:08

Решение:

Для решения задачи, давайте разберем ее по шагам.

Шаг 1: Понимание входных данных

- vmax: максимальная скорость черепахи в см/мин.
- d: время, необходимое для поедания одуванчика в минутах.
- N: количество одуванчиков.
- Каждая пара (xi, ti) представляет собой расстояние до одуванчика и время его прорастания.

Шаг 2: Преобразование времени

Время прорастания одуванчиков задано в формате hh:mm. Мы можем преобразовать это время в минуты с начала суток для удобства расчетов.

Шаг 3: Расчет времени

1. Время в пути: Для каждого одуванчика мы можем рассчитать время, необходимое для его достижения. Время в пути до одуванчика на расстоянии xi будет равно \( \frac{xi}{vmax} \).
2. Общее время: Для каждого одуванчика нужно учитывать время его прорастания. Если черепаха прибывает до момента прорастания, она должна ждать, пока он прорастет.
3. Поедание одуванчиков: После достижения одуванчика черепаха тратит d минут на его поедание.

Шаг 4: Итерация по одуванчикам

- Начинаем с времени 0 (полночь).
- Для каждого одуванчика:
- Рассчитываем время в пути.
- Проверяем, нужно ли ждать прорастания.
- Добавляем время на поедание.