Олимпиадная задача Черепаха

Question

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

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

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

Алгоритм решения: бинарный поиск в интервале от 0 до максимального времени прорастания. Ищем середину. Если получилось, что время, в которое мы подползли к одуванчику больше либо равно времени прорастания этого одуванчика, то увеличиваем счетчик количества съеденных одуванчиков и к времени прибавляем d. После того, как прошлись по всем одуванчикам, кроме последнего, прибавляем к общему времени, время, за которое черепаха проползет расстояние от предпоследнего до последнего одуванчика. Теперь, если время равно времени прорастания одуванчика - то на выход, если больше - то идем в левый интервал, если меньше то в правый.

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

import math

v, d = map(int, input().split())
n = int(input())
R = []
T = []
for i in range(n):
    x, t =input().split()
    x = int(x)
    h, m = map(int, t.split(":"))
    if i == 0:
        R.append(x)
    else:
        R.append(x-R[i-1])
    T.append(float(h*60+m))
    if i == n-1:
        z = x
L = 0
PR = max(T)
k = 0
while PR-L > 0:
    M = (L+PR)/2
    t = M
    for i in range(len(R)-1):
        t += R[i]/v
        if t >= T[i]:
            t += d
            k += 1
    t += R[-1]/v
    if t == T[-1]:
        break
    elif t > T[-1]:
        PR = M
    else:
        L = M
t += z/v+(n-k)*d
t = math.ceil(t)
h = t//60
m = t%60
print(str(h).zfill(2)+":"+str(m).zfill(2))

Answer 1

В общем, я постарался минимально изменять ваш код, чтобы он залетел:

import math

v, d = map(int, input().split())
n = int(input())
R = []
T = []
z = 0
for i in range(n):
    x, t =input().split()
    x = int(x)
    h, m = map(int, t.split(":"))
    R.append(x-z)
    T.append(float(h*60+m))
    z = x

L = 0
PR = max(T)
for i in range(100):
    M = (L+PR)/2
    t = M
    for i in range(len(R)-1):
        t += R[i]/v
        if t >= T[i]:
            t += d
    t += R[-1]/v
    if t == T[-1]:
        break
    elif t > T[-1]:
        PR = M
    else:
        L = M

t = 2*z/v+n*d+PR
t = math.ceil(t)
h = t//60
m = t%60
print(str(h).zfill(2)+":"+str(m).zfill(2))

Изменения затронули вашу ошибку во вводе, когда вы при расчете разницы между двумя соседними иксами считали разницу между иксом и предыдущей разницей.

Также я изменил вид цикла и расчет t после него. Почему-то без обоих этих изменений у меня не получалось загнать ваш код.

БЛОГ НА HUSL

Олимпиадная задача Черепаха

Ответы (1 шт):