Задача 1. Два станка

Автор:Даниил Орешников   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

На производстве имеется два станка. Необходимо изготовить как можно больше деталей за сегодняшнюю смену, продолжительность которой k минут.

Станки находятся в законсервированном состоянии. Для того, чтобы ввести в строй первый станок, требуется a минут, после чего он будет производить x деталей в минуту. Для того, чтобы ввести в строй второй станок, требуется b минут, после чего он будет производить y деталей в минуту.

Для введения в строй станка требуется присутствие инженера, поэтому нельзя вводить в строй два станка одновременно. При этом введение станка в строй и изготовление деталей на другом станке, а также одновременное изготовление деталей на двух станках разрешается.

Требуется выяснить, какое максимальное количество деталей удастся изготовить за k минут.

Формат входных данных

В первой строке ввода дано единственное целое неотрицательное число k — количество минут в смене.

Во второй строке ввода даны целые неотрицательные числа a и x — время введения первого станка в строй и количество деталей, которое он изготавливает за одну минуту.

В третьей строке ввода даны целые неотрицательные числа b и y — время введения второго станка в строй и количество деталей, которое он изготавливает за одну минуту.

Формат выходных данных

Выведите единственное число — максимальное количество деталей, которое удастся изготовить за смену.

Обратите внимание, что ответ в этой задаче может быть довольно большим и не помещаться в 32-битные типы данных. Рекомендуется использовать 64-битный тип данных, например long long в C++ или int64 в Паскале.

Ограничения

0 ≤ k ≤ 109, 0 ≤ a, x ≤ 109, 0 ≤ b, y ≤ 109

Система оценки

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
117a = 0, x = 0полная
214a = 0, b = 0полная
320a = b2первая ошибка
420x = yпервая ошибка
529нет1 — 4первая ошибка

Пояснение к примеру

В примере выгодно сначала ввести в строй второй станок и за оставшиеся 15 минут изготовить 45 деталей, а затем ввести в строй первый и за оставшиеся 5 минут изготовить на нём еще 20 деталей.

Если сначала ввести в строй первый станок и изготовить на нем в оставшиеся 10 минут 40 деталей, то после введения в строй второго на нем удастся изготовить лишь 15 деталей, суммарно 55, что меньше, чем 65.

Примеры тестов

Стандартный вход Стандартный выход
1
20
10 4
5 3
65

Разбор

В первых четырех подзадачах достаточно легко найти конкретную формулу, которая позволяет найти ответ. Обозначим искомое количество деталей как r.

Подзадача 1

Если a = 0 и x = 0, то первый станок вообще нет смысла использовать. Введем в строй второй и получим ответ: r = b ⋅ max(k − b, 0).

Важно не забыть, что время на запуск может оказаться больше k, и тогда количество деталей будет равно 0, для чего мы и берем max в формуле.

Подзадача 2

Если a и b равны нулю, то можно сразу запустить оба станка в работу и получить ответ: r = (x + y) ⋅ k.

Подзадача 3

Когда a = b, выгодно сначала ввести в строй наиболее производительный станок, и сразу после этого начать вводить в строй второй. Ответ тогда будет равен: r = max(x, y) ⋅ max(k − a, 0) + min(x, y) ⋅ max(k − 2a, 0).

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

Подзадача 4

Если станки производят детали с одинаковой скоростью, то требуется ввести в строй сначала тот, на запуск которого уйдет меньше времени, чтобы детали раньше начали производиться. Получаем: r = a ⋅ max(k − min(a, b), 0) + a ⋅ max(k − a − b, 0).

Подзадача 5

Теперь посмотрим как решать общий случай. Переберем два варианта: какой станок будем вводить в строй первым. Если мы сначала введем в строй первый станок, ответ будет: r1 = x ⋅ max(k − a, 0) + y ⋅ max(k − a − b, 0).

Наоборот, если сначала ввести в строй второй, то получим: r2 = y ⋅ max(k − b, 0) + x ⋅ max(k − a − b, 0).

Чтобы получить ответ на задачу, достаточно взять максимум из двух этих значений: r = max(r1, r2).

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


0.076s 0.013s 13