Задача про черепаху и одуванчики
Помогите, пожалуйста, дорешать задачу. Несколько тестов не проходят. Или напишите, какие тесты стоит проверить. Заранее спасибо!
Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени, и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины 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), округленный до целых минут в большую сторону.
Примечания
В часе – 60 минут, в сутках – 24 часа.
Время в сутках изменяется от 00:00 до 23:59.
Можете считать, что черепаха не меняет направления движения до тех пор, пока не доползет до последнего одуванчика.
Если вкратце то я шел по одуванчикам и ел их так, чтобы прийти максимально в притык к моменту прорастания последнего одуванчика
def roundx(x):
if x == int(x):
return x
return int(x + 1)
def cn2(time):
h = int((time // 60) % 24)
m = int(time % 60)
h = '0' * (2 - len(str(h))) + str(h)
m = '0' * (2 - len(str(m))) + str(m)
return str(h) + ':' + str(m)
def cn(ts):
s = ts.split(':')
return int(s[0]) * 60 + int(s[1])
def time_d(s, v):
return s / v
f = open('input.txt', 'r', encoding = 'UTF-8')
v, t = map(int, f.readline().split())
n = int(f.readline().strip())
time = 0
xo = 0
cnt_time = 0
time_prx = []
for line in f:
st = line.split()
s = float(st[0])
tp = cn(st[1])
time_prx.append([float(s), float(tp)])
t_pr_lst = time_prx[-1]
for p in time_prx:
time += time_d(p[0] - xo, v)
xo = p[0]
if time >= p[1]:
time += t
else:
if p[1] + time_d(t_pr_lst[0] - xo, v) + t - t_pr_lst[1] <= 0.1:#!!+t
time += p[1] - time + t
else:
if p[1] == t_pr_lst[1]:
time = t_pr_lst[1] + t
else:
cnt_time += t
with open('output.txt', 'w', encoding = 'UTF-8') as fo:
print(cn2(roundx(time + cnt_time + time_d(xo, v))), file = fo)
f.close()
Ответы (1 шт):
Код не пишу, пишу только идею. Переформулируем немного задачу. Идти до конца и обратно всё равно придётся. Можно всегда двигаться с максимальной скоростью, а потом ждать. Есть все одуванчики тоже придётся. Таким образом нам нужно минимизировать время ожидания. При d=0
очевидно что оптимальная стратегия это идти до последнего одуванчика, ждать если нужно и идти обратно. Так же, не нарушая общности, ждать можно в начале пути. (несложно доказать). В задании сказано
до следующей полуночи вернуться домой
Но это не сильно важно на самом деле. Для простоты рассуждений время будем измерять в <минутах/скорость>
. Таким образом, что бы за 1 единицу времени проходилось расстояние в 1 сантиметр. (Можно и без этого, но так для понимания проще). В сутках 1440 минут, скорость не более 200, итого 288 000
.
Таким образом решение за O(N*V*1400)
Просто в лоб переберём начальное время выхода и сделаем симуляцию. Если одуванчик готов, то едим его на пути вперёд, иначе на обратном. Если пришли в последнюю точку, а там нужно ждать, то откидываем такой вариант, он в других будет рассмотрен.
Но это не очень хорошо и быстро. Подумаем ещё раз, ответ - это время на движение до конца и обратно плюс время на поедание одуванчиков плюс задержка. Нам нужно найти минимальную задержку, такую что мы дойдём до конца без простоев. Уже напрашивается решение за O( N * log(V*1440) )
- это бинарный поиск по ответу. Как реализовать - думаю проблем не составит.
P.S. по возможности избегайте дробных чисел, там могут быть проблемы с точностью.