Задача на ксерокопии

Question

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

Сегодня утром жюри решило добавить в вариант олимпиады ещё одну, Очень Лёгкую Задачу. Ответственный секретарь Оргкомитета напечатал её условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать ещё N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой — за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

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

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

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

Ввод: 4 1 1 Вывод: 3

Ввод: 5 1 2 Вывод: 4

Код:

uint64_t foo(uint64_t count, uint64_t a, uint64_t b)
{
    uint64_t res { static_cast<uint64_t>(std::ceil(static_cast<double>(count * a * b) / (a + b))) };
 
    uint64_t rem_x { res % a };
    uint64_t rem_y { res % b };
    
    if(rem_x && rem_y)
        res += std::min(a - rem_x, b - rem_y);
 
    return res;
}
 
uint64_t bar(uint64_t count, uint64_t a, uint64_t b)
{
    if(!count)
        return 0;
 
    return std::min(a, b) + foo(--count, a, b);
}

Answer 1

Мне не очень понятно ваше решение. Я бы решал так...
Сначала на более быстром ксероксе (пусть x) делаем копию, потом шлепаем на быстром M копий, на медленном N-1-M. Очевидно, что полное время

T = x + max(x*M,y*(N-1-M))

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

x*M = y*(N-1-M)

откуда решение возле M = y*(N-1)/(x+y). Вот и проверим пару значений в поисках минимума - на 1 меньше и на 1 больше, сильнее вряд ли будут отличаться...

int main()
{
    int N, x, y;
    cin >> N >> x >> y;
    if (x > y) swap(x,y);

    int M = y*(N-1)/(x+y);
    int T = x + max(x*M,y*(N-1-M));
    for(int m = max(0,M-1); m <= min(N-1,M)+1; ++m)
    {
        int t = x + max(x*m,y*(N-1-m));
        if (t < T) T = t;
    }
    cout << T;
}

Тут это решение проходит на ура...

БЛОГ НА HUSL

Задача на ксерокопии

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