jeerjmin
@jeerjmin

Как оптимизировать простенький код?

Есть такая задача
Принтеры работают с неодинаковой скоростью. Один печатает страницу за X секунд, а другой за Y.
И вот теперь Джон и Мэри пытаются подсчитать какое минимальное время они могут затратить на печать всего документа.
Входные данные содержат количество тест-кейсов в первой строке.
Далее следуют сами тесты по одному в каждой строке.
Каждый из них содержит по три целых числа - X Y N, где N не превышает 1,000,000,000.
Ответ должен содержать минимальные времена печати для каждого случая, через пробел.

Я решил ее для небольших входных значений.
Но если взять s1=24342423 s2= 23423413 pages=45234524
То все встанет.
Подскажите алгоритм

def twoprinters(s1,s2,pages):
    seconds=1
    r=0
    while True:
            r=(int(seconds/s1)+int(seconds/s2))
            if r>=pages:break
            else:
                seconds=seconds+1
                
 
    return seconds
  • Вопрос задан
  • 474 просмотра
Решения вопроса 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Оптимизировать неправильное решение бесполезно. Тут 2 варианта:
1) Реализовать бинарный поиск. У вас уже правильная идея, как определить, что за заданное количество секунд можно напечатать сколько надо или больше страниц (floor(seconds/s1)+floor(seconds/s2) >= n). Теперь осталось вместо линейного увеличения seconds, удваивать его. Т.е. вместо seconds = seconds+1 делать seconds = seconds*2. После чего сделать бинарный поиск на отрезке [1,seconds].

2) Применить математику. Нужно найти минимальное x такое, что floor(x/s1)+floor(x/s2) >= n.

Забъем на округление и решим x/s1 + x/s2 >= n.
x = ceil(n*s1*s2/(s1+s2)).

Но. это будет оценка сверху, потому что мы выкинули округления, которые уменьшают реальное значение количества напечатанных за x секунд страниц. Но, внимание, реальное количество страниц будет максимум на 2 страницы меньше, потому что oкругление сбивает максимум 1 страницу.

Теперь будем увеличивать x, чтобы увеличить количество напечатанных страниц. Если просто прибавлять 1 каждый раз, то почти всегда занчение не поменяется, потому что x/s1 так и будет дробным. Увеличение произойдет только когда x/s1 или x/s2 будет целым. Следующее такое число можно легко найти (это будет x, делящееся на s1 или s2. Итак, решение:

def twoprinters(s1,s2,pages):
    seconds= int(pages*s1*s2 + s1 + s2 - 1)/(s1+s2)
    while int(seconds/s1)+int(seconds/s2) < pages:
            a = seconds - seconds%s1 + s1
            b = seconds - seconds%s2 + s2
            seconds = min(a,b)


Этот код будет работать мгновенно для очень больших чисел. Потому что цикл while тут будет исполнятся максимум 2 раза. Каждый раз значение напечатанных страниц будет увеличиваться как минимум на 1, а оно изначально будет максимум на 2 меньше ответа. Странные вычисления a и b - это следующие числа за seconds, которые делятся на s1 и s2 соответственно. Мы вычитаем остаток от деления и получаем предыдущее или равное seconds число, делящееся на s1 и s2. Прибавляя s1 или s2 мы получаем следующее число, как нам и надо.
Ответ написан
Комментировать
longclaps
@longclaps
a, b, n = 2, 3, 4  # 2сек/лист, 3сек/лист, 4 листа
ab = a + b
print(min(a * (n - n * a // ab), b * (n - n * b // ab)))
Ответ написан
jeerjmin
@jeerjmin Автор вопроса
Вывел приближенное значение времени из выражения, которое можно присвоить начальному значению.
И все начало работать быстро )

seconds=int((pages*s1*s2)/(s1+s2))
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
thematdev
@thematdev
Плагинёр
Я конечно понимаю, что пайтон медленный(ибо изжопыкомпиляция по строчкам), но оптимизацию все равно сделал:
seconds=1
    r=0

Напиши вне войда ибо не нужно каждый раз инициализировать переменную.
Также зачем проверять на if/else? Поставь проверку
if (r<pages):
    seconds += 1

И поставь оператор начать цикл сначала(забыл его))), а если не дойдёт, то брейк -> проверок на 1 меньше.
И забудь о foo = foo+1, есть же +=
А если всё опять встанет, то пиши на Java!
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы