Question

Есть две копировальных машины, одна делает копию документа за x минут, а вторая — за y минут. Требуется получить n копий некоторого документа. За какое минимальное время это возможно сделать? Изначально документ существует в одном экземпляре. Формат ввода В единственной строке даны три числа, разделенные пробелом: N, x, y (1 ≤ x, y ≤ 10, 1 ≤ N ≤ 2*108). Формат вывода Выведите одно число — минимальное время, за которое можно получить n копий документа (в минутах).

Answer 1

#include <iostream>

typedef long long   ll;

using namespace std;

bool ll_is_valid(ll t, ll N, ll x, ll y)

{

return  t / x + (t - x) / y >= N;

}

ll f(ll N, ll x, ll y)

{

   ll R = 1;

   while (!ll_is_valid(R,N,x,y)) R *= 2;

ll L = R / 2;

while(R - L > 1)

{

 ll M   =   (L + R) / 2;

 

 if (!ll_is_valid(M,N,x,y)) {L = M;}

 else {R = M;}

}

return  R;

}

int  main()

{

ll N,x,y;

cin >> N >> x >> y;

if(x > y) swap( x, y );  

cout << f(N, x, y) <<  std::endl;

}

Answer 2

Для решения данной задачи, нужно определить, сколько копий можно сделать за время t. Затем, используя бинарный поиск по времени, найти минимальное значение t, которое позволит сделать N копий документа.

Итак, вот алгоритм решения:

1. Читаем входные данные N, x и y.
2. Устанавливаем нижнюю границу бинарного поиска left = 1 (минимальное время - одна минута) и верхнюю границу right = N * min(x, y) (максимальное время - если обе машины работают параллельно).
3. Выполняем бинарный поиск, пока left < right:
   • Устанавливаем среднее значение времени mid = (left + right) / 2.
   • Вычисляем, сколько копий можно сделать на обеих машинах за время mid: copies_x = mid / x и copies_y = mid / y.
   • Общее количество сделанных копий copies_total = copies_x + copies_y.
   • Если copies_total >= N, значит, мы можем сделать достаточное количество копий, и мы должны сузить верхнюю границу времени: right = mid.
   • В противном случае, увеличиваем нижнюю границу времени: left = mid + 1.
4. Когда бинарный поиск закончен, минимальное время будет храниться в переменной left. Выводим её как результат.

И вот Python код реализации:

pythonCopy code
def min_time_to_make_copies(N, x, y):
    left = 1
    right = N * min(x, y)

    while left < right:
        mid = (left + right) // 2
        copies_x = mid // x
        copies_y = mid // y
        copies_total = copies_x + copies_y

        if copies_total >= N:
            right = mid
        else:
            left = mid + 1

    return left

# Чтение входных данных
N, x, y = map(int, input().split())

# Вычисление и вывод результата
result = min_time_to_make_copies(N, x, y)
print(result)

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