Помогите решить олимпиадную задачу про вырубку леса

Question

Решаю олимпиадную задачу про вырубку леса.

Условие:

Фермер Николай нанял двух лесорубов: Дмитрия и Фёдора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т. д.

Фёдор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Фёдор отдыхает в M-й, 2M-й, 3M-й день, и т. д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A+B деревьев, в дни, когда отдыхает только Фёдор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Я написал решение, но тестирующая система выдаёт TL в некоторых тестах. Подскажите пожалуйста как его можно оптимизировать?

a, k, b, m, x = map(int, input().split())
finished = 0
day = 0
while True:
    day += 1
    if finished >= x:
        break
    if day % k != 0:
        finished += a
    if day % m != 0:
        finished += b
print(day - 1)

Answer 1

С помощью бинарного поиска найдите наименьшее значение n, для которого

 (n - n // k) * A + (n - n // m) * B  >= X

Answer 2

X=int(input("Количество деревьев: "))
A=int(input("Скорость Дмитрия: "))
K=int(input("Частота отдыха Дмитрия: "))
B=int(input("Скорость Федора: "))
M=int(input("Частота отдыха Федора: "))

day=0 #сколько дней прошло
while X>0:
  day+=1
  if not day%K==0:
    X-=A

  if not day%M==0:
    X-=B

print(day)

Вот так. Один шаг цикла=1 день. Проверяем отдых через проверку остатка текущего дня по модулю частоты отдыха.

P.S. Input можно делать как угодно, просто я предпочитаю построчно каждую переменную вводить.

Answer 3

Основываясь на ответе MBo, предложу такой код:

def bmin(X, A, k, B, m, lst):
    if (k == 1) and (m == 1):
        return 'Impossible'
    if not lst:
        return X
    mid = len(lst) // 2
    n = lst[mid]
    if (n - n // k) * A + (n - n // m) * B  >= X:
        return min(n, bmin(X, A, k, B, m, lst[:mid]))
    return bmin(X, A, k, B, m, lst[mid+1:])

X = 1000000
A = 10; k = 3
B = 15; m = 4
days = bmin(X, A, k, B, m, range(X//min(A, B)))
print(days)

timeit показал ускорение в 2-2.5 раза от вашего кода.

Answer 4

Нерекурсивный бинарный поиск по ответу, придерживающийся неравенства, предложенным MBo ((n - n // k) * A + (n - n // m) * B >= X, где n - минимально и является ответом на задачу).

Следующий код проходит проверку на Сириусе и Informatics:

a, k, b, m, x = map(int, input().split())
L, R = 0, x * max(a, b)

while R - L > 1:
  M = (L + R) // 2
  if (M - M // k) * a + (M - M // m) * b >= x:
    R = M
  else:
    L = M

print(R)

БЛОГ НА HUSL

Помогите решить олимпиадную задачу про вырубку леса

Условие:

Я написал решение, но тестирующая система выдаёт TL в некоторых тестах. Подскажите пожалуйста как его можно оптимизировать?

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