Задача 56: Черепаха (XIV Всероссийская
олимпиада по информатике)
Домик черепахи расположен в начале прямой узкой грядки, на которой
должны прорасти одуванчики - ее любимое лакомство. И вот черепахе
приснился вещий сон. Из него она узнала, что наконец-то после
полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент
времени и в какой точке грядки вырастет каждый одуванчик. Ровно в
полночь черепаха выползла из домика, чтобы съесть все одуванчики и
до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины vmax.
Одуванчик она съедает, остановившись на время d. Если одуванчик
начать есть, но не доесть до конца, то он засыхает, поэтому его надо
съедать за один прием. Одуванчики прорастают тем позже, чем дальше
они расположены от начала грядки. В одной точке не могут прорастать
несколько одуванчиков, а также несколько одуванчиков не могут
прорастать в один момент времени.
Требуется определить, в какой момент времени черепаха сможет
вернуться домой, съев все одуванчики и затратив на путешествие
наименьшее время.
Входные данные
В 1-й строке файла turtle.in находятся 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). Пары приведены в порядке возрастания расстояний.
Входные данные гарантируют, что черепаха может съесть все одуванчики
и вернуться домой в течение суток.
Выходные данные
Файл turtle.out должен содержать момент времени возвращения
черепахи домой (в формате hh:mm), округленный до целых минут в
большую сторону.
Пример
Входной файл turtle.in
3 1
1
100 00:01
Выходной файл turtle.out
01:08
Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Частичные решения для случая d = 0 будут оцениваться.
Решение:
Опять задачка со Всероссийской олимпиады 2002 года. И опять там я ее
решил только наполовину :( эвристически. Кстати мое эвристическое
решение получилось длиннее и запутанней правильного.
Теперь перейдем к изложению основной идеи решения.
Во-первых необходимо считать входные данные. Время прорастания я
преобразовывал в минуты, а расстояние от начала грядки - как
расстояние от предыдущего одуванчика до этого. Т.е. у меня от
расстояния от начала до данного одуванчика отнималось расстояние от
предыдущего одуванчика до начала грядки.
Ввод данных в этой задаче достаточно муторное дело - писал минут
10-15.
Теперь подумаем над алгоритмом, по которому черепаха должна есть
одуванчики. Естественно, что по пути к последнему одуванчику она
должна есть все, что уже проросли, потом съесть последний одуванчик,
а затем возвращаться и есть все (они уже проросли раньше
последнего). Но возникает одна проблема: а что если мы придем, а
последний одуванчик еще не вырос? Надо ждать, причем ждать не у
последнего одуванчика, а в самом начале грядки. Это объясняется тем,
что, задержавшись в начале грядки, мы сможем съесть больше
одуванчиков по пути туда и меньше оставить на обратный путь.
Задача решается дихотомией. Минимум - нулевая задержка, максимум -
время прорастания последнего одуванчика - условие выхода - если
пришли ровно к всходу последнего одуванчика или максимум минус
минимум меньше 0.1 минуты (для верности). У нас будет переменная,
отвечающая за задержку, значение которой будет равно (max + min) / 2
(обозначим эту переменную wait). Также у нас будет переменная, в
которой храниться значение времени в данный момент (time). При входе
в цикл считаем wait, а затем time := wait. Теперь идем по всем
одуванчикам от первого до предпоследнего. К времени прибавляем время
проползания от предыдущего одуванчика к следующему (time := time + x[i]
/ vmax). Если получилось, что время, в которое мы подползли к
одуванчику больше либо равно времени прорастания этого одуванчика,
то увеличиваем счетчик количества съеденных одуванчиков и к времени
прибавляем d.
После того, как прошлись по всем одуванчикам, кроме последнего,
прибавляем к общему времени, время, за которое черепаха проползет
расстояние от предпоследнего до последнего одуванчика. Теперь, если
время равно времени прорастания одуванчика - то на выход, если
больше - то max := wait, если меньше - min := wait.
Теперь мы определили нужную задержку и нам известно время,
затраченное на путь до последнего одуванчика. Также известно, что к
этому времени он уже пророс. Чтобы получить итоговое время, надо к
этому времени прибавить время на съедение оставшихся одуванчиков (мы
знаем, сколько мы съели на пути туда) и время на обратную дорогу
(просто разделить расстояние от начала до последнего одуванчика на
скорость). Ответ готов. Осталось только преобразовать его к нужному
формату.
Моя программа прошла все тесты, кроме одного. Там у жюри ответ
получился 19:00, а у меня 19:01. Оказывается жюри округляло число по
двум знакам после запятой, а различие пошло в третьем знаке. Моя
программа верно посмотрела, что количество минут не целое и
прибавило еще одну дополнительную минуту. А, оказывается, не надо
было. Пришлось это обработать отдельно.
Далее
ð
