Два принтера

21 Август 2019 - Время чтения: 26 минуты

Условие задачи: В офисе стоят два принтера, первый печатает страницу за A секунд, второй - за B секунд. Найти минимальное время, за которое эти принтеры напечатают N страниц, причём N может достигать миллиарда.

Как это часто бывает, на первый взгляд задача тривиальна. Если одна страница печатается A секунд, значит принтер печатает 1/A страниц в секунду. Второй, соответственно, 1/B страниц в секунду. В сумме 1/A + 1/B страниц в секунду. N страниц будут напечатаны за N / (1/A + 1/B) секунд. Правильно? Неправильно! В чём же ошибка?

В том, что нас не интересует средняя скорость принтера, например 1/10 страницы в секунду, если он печатает одну страницу 10 секунд. Нас интересует количество страниц, отпечатанных полностью. Допустим, этот принтер, который печатает одну страницу 10 секунд, будет работать 19 секунд. Сколько он успеет напечатать? Одну страницу! А формула предполагает, что он напечатает "почти две" страницы, и соответственно результат получится неверным.

Поэтому я предлагаю воспользоваться обратной формулой: рассчитать количество страниц, которые будут напечатаны за определённое время. Это можно подсчитать абсолютно точно: N = t/A + t/B, где t - это время.

Очевидно, что с возрастанием количества страниц, которые нужно напечатать, время будет тоже возрастать, или по крайней мере не убывать. То есть задача сводится к поиску значения неубывающей функции. Можно применить обычный бинарный поиск, надо только выбрать минимальное и максимальное возможное время, чтобы знать, в каком промежутке искать. Можно, конечно, бесхитростно положить:

tmin = 1

tmax = N * min(A, B).

Но хотелось бы выбрать границы как-нибудь так, чтобы они были как можно более узкими. Допустим, первый принтер печатает страницу 3 секунды, а второй - 5. Очевидно, что за 15 секунд первый принтер напечатает 5 страниц, а второй - 3. В сумме 8. Если число страниц делится на 8 нацело, то можно точно рассчитать время по формуле:

tmin = N * A * B / (A + B)

Это та же самая формула, только преобразованной по правилам математики, чтобы считать в целых числах. Она даст верный ответ, если N делится на A + B нацело. А если нет? Давайте подумаем. Можно представить работу принтеров так: за каждый цикл из A * B секунд они печатают A + B страниц. Найдём минимальное и максимальное количество циклов. Очевидно, минимальное количество циклов равно N / (A + B). А максимальное отличается на единицу. Останется только найти точное время внутри цикла с помощью бинарного поиска.


Исходный код на Python
n, a, b = map(int, input().split())
cycles, remain = divmod(n, a + b)
tmin = cycles * a * b
 
if remain != 0:
    tmin += min(a, b)
    tmax = (cycles + 1) * a * b
    while tmin < tmax:
        t = (tmin + tmax) // 2
        if t // a + t // b < n:
            tmin = t + 1
        else:
            tmax = t
 
print(tmin)

Исходный код на C#
using System;
using System.Linq;
 
class Program
{
    public static void Main()
    {
        long[] nab = Console.ReadLine().Split().Select(Int64.Parse).ToArray();
        long n = nab[0];
        long a = nab[1];
        long b = nab[2];
        long remain;
        long cycles = Math.DivRem(n, a + b, out remain);
        long tmin = cycles * a * b;
        if (remain != 0)
        {
            tmin += Math.Min(a, b);
            long tmax = (cycles + 1) * a * b;
            while (tmin < tmax)
            {
                long t = (tmin + tmax) / 2;
                if (t / a + t / b < n)
                {
                    tmin = t + 1;
                }
                else
                {
                    tmax = t;
                }
            }
        }
        Console.WriteLine(tmin);
    }
}

Исходный код на C++
#include <algorithm>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    lldiv_t cycles = lldiv(n, a + b);
    long long tmin = cycles.quot * a * b;
    if (cycles.rem != 0) {
        tmin += min(a, b);
        long long tmax = (cycles.quot + 1) * a * b;
        while (tmin < tmax) {
            long long t = (tmin + tmax) / 2;
            if (t / a + t / b < n) {
                tmin = t + 1;
            } else {
                tmax = t;
            }
        }
    }
    cout << tmin << endl;
    return 0;
}

Исходный код на C99
#include <stdio.h>
 
typedef struct {
    long long quot;
    long long rem;
} lldiv_t;
 
lldiv_t lldiv(long long a, long long b) {
    lldiv_t d;
    d.quot = a / b;
    d.rem = a % b;
    return d;
}
 
int main(void)
{
    long long n, a, b;
    scanf("%lld%lld%lld", &n, &a, &b);
    lldiv_t cycles = lldiv(n, a + b);
    long long tmin = cycles.quot * a * b;
    if (cycles.rem != 0) {
        tmin += a < b ? a : b;
        long long tmax = (cycles.quot + 1) * a * b;
        while (tmin < tmax) {
            long long t = (tmin + tmax) / 2;
            if (t / a + t / b < n) {
                tmin = t + 1;
            } else {
                tmax = t;
            }
        }
    }
    printf("%lld\n", tmin);
    return 0;
}

Единственный вопрос, который может возникнуть: зачем мы добавляем к tmin минимальное из чисел A и B, а не единицу? Если времени нам не хватило, значит ненапечатанной осталась по крайней мере одна страница. Логично предположить, что если произошло именно так, то эта единственная страница будет напечатана на самом быстром принтере. На это уйдёт A или B секунд, смотря какое число меньше. Чуть-чуть сужаем поиск.

Кроме того, я написал свою реализацию функции lldiv на языке C. Можно было бы без этого обойтись, и просто посчитать делитель и остаток. Но я решил сделать так, как сделал, для единообразия решений. А функции lldiv в языке C может и не оказаться. В моём компиляторе её, например, нет. Хотя в стандарте C99 она присутствует.

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории