<ПРЕД Задача:
СЛЕД>
Задачу решили 38 пользователей: defrager, Kuznetsov_S, DAV, DmitrievVladimir814, M_A_X, risinka_814, yura814, gafrustam814, Alexeyev814, alatkon, zloy_mipt, avg79, shatalin_814, brain-001, coolzero814, WsemirZ, KZ, Philip_PV, RAVEman, topspin, asp, stasg7, fetetriste, VladimirChelnokov, Logger067, Dest, tttttt, vitar, neko, mariama, checkil, mikelan, Azizkhan, NIGHTFIT, mathematic, basimova, dzhavaharnal, JohnJones_001.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Черепаха

Time limit = 3 секунды

Memory limit = 32 Mb

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

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

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

Вход В 1-й строке находятся 2 целых числа, разделенные пробелом: V_max (в см/мин) и d (в минутах), 0 < V_max ≤ 200, 0 ≤ d ≤ 500. Во 2-й строке находится число N — количество одуванчиков (в штуках). 0 ≤ N ≤ 1400 при d = 0, в противном случае 0 ≤ N ≤ 200. В каждой из последующих N строк расположены: целое число x_i — расстояние от одуванчика до начала грядки (в сантиметрах), 0 ≤ x_i ≤ 32767, и через пробел t_i — момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний. Входные данные гарантируют, что черепаха может съесть все одуванчики и вернуться домой в течение суток.

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

Вход#1
3 1 
1
100 00:01
Выход#1
01:08

Автор:
XIV Всероссийская олимпиада по информатике, 2 тур, Пермь.
5-11 апреля 2002 года

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.237.183.249