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

Question

[mr jeery]

Есть такая задача
Принтеры работают с неодинаковой скоростью. Один печатает страницу за 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

Answer 1

[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 мы получаем следующее число, как нам и надо.

Answer 2

[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)))

Comments

[Wataru]

Прокомментируйте, пожалуйста, как это работает, как вы вывели эту формулу?

[longclaps]

wataru
варианты:
- первый распечатает n*b//(a+b) листов, а второй - оставшиеся (n - n*b//(a+b)) за (n - n*b//(a+b)) * b сек, второй будет печатать столько же времени плюс, возможно, 1 лист
- наоборот
возможно, они потребуют одинаковое время, а может и нет

Answer 3

[mr jeery]

Вывел приближенное значение времени из выражения, которое можно присвоить начальному значению.
И все начало работать быстро )

seconds=int((pages*s1*s2)/(s1+s2))

Comments

[longclaps]

Нежелание читать чужие ответы - это хамство или тупость?

[Roman K]

longclaps, требую добавить пункт жалобы "ТС мудак"

[mr jeery]

longclaps, не понял откуда вы взяли выражение, я вставил его в код, он выдает совсем не те значения, что нужно и дольше чем мое решение

[longclaps]

Олег Тарасов, неужели? тест в студию.

[mr jeery]

longclaps, все проверил. был не прав. искренне прошу прощения за невежество!

[longclaps]

Олег Тарасов,
прочти про целочисленное деление.
варианты:
- первый распечатает n*b//(a+b) листов, а второй - оставшиеся (n - n*b//(a+b)) за (n - n*b//(a+b)) * b сек
- наоборот
возможно, они потребуют одинаковое время, а может и нет

Answer 4

[thematdev]

Я конечно понимаю, что пайтон медленный(ибо изжопыкомпиляция по строчкам), но оптимизацию все равно сделал:

seconds=1
    r=0

Напиши вне войда ибо не нужно каждый раз инициализировать переменную.
Также зачем проверять на if/else? Поставь проверку

if (r<pages):
    seconds += 1

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

Comments

[longclaps]

А если всё опять встанет, то пиши еще.