Задача на нахождение минимального времени копирования на двух ксероксах

Question

Не могу понять откуда берётся T и M, также не могу понять нижнюю и верхнюю границу цикла соответственно:

Сегодня утром жюри решило добавить в вариант олимпиады ещё одну "Очень Легкую Задачу". Ответственный секретарь Оргкомитета напечатал её условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать ещё N копий.

В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y.

Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.

Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные

На вход программы поступают три натуральных числа N, x и y, разделённые пробелом (1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).

Выходные данные

Выведите одно число – минимальное время в секундах, необходимое для получения N копий.

Примеры:

Входные данные
4 1 1
Выходные данные
3
Входные данные
5 1 2
Выходные данные
4

Код:

def min_time(N, x, y):
    if x > y:
        x, y = y, x

    M = y * (N - 1) // (x + y)
    T = x + max(x * M, y * (N - 1 - M))
    for m in range(max(0, M - 1), min(N - 1, M) + 2):
        t = x + max(x * m, y * (N - 1 - m))
        if t < T:
            T = t
    return T

N, x, y = map(int, input().split())
print(min_time(N, x, y))

Answer 1

Скопируйте скрипт в test.py и запустите:

import os

print("-" * 50 + "\nМинимальное время копирования на 2-х ксероксах:\n" + "-" * 50)

def min_time_to_copy(N = 1, x = 1, y = 1):

 # Если x больше y, меняем их местами, чтобы x всегда был меньше или равен y
 if x > y: x, y = y, x

 # Начальное значение left должно быть x, так как первая копия занимает x секунд
 left, right = x, N * x

 # Бинарный поиск для нахождения минимального времени
 while left < right:
  mid = (left + right) // 2  # Среднее значение между left и right

  # Проверяем, можем ли мы сделать N копий за mid секунд
  if (mid // x) + (mid // y) >= N + 1:  # Учитываем первую копию
   right = mid  # Если можем, сужаем правую границу
  else:
   left = mid + 1  # Если не можем, сужаем левую границу

 return left

# Пример использования
print('''Параметры:
N - количество копий (шт.),
x - время печати копии на первом принтере (сек),
y - время печати копии на втором принтере (сек)''')
N, x, y = map(int, input("Введите параметры: ").split())
print(min_time_to_copy(N, x, y))

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

БЛОГ НА HUSL

Задача на нахождение минимального времени копирования на двух ксероксах

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