| Автор: | Даниил Орешников | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 17 | a = 0, x = 0 | полная | |
| 2 | 14 | a = 0, b = 0 | полная | |
| 3 | 20 | a = b | 2 | первая ошибка |
| 4 | 20 | x = y | первая ошибка | |
| 5 | 29 | нет | 1 — 4 | первая ошибка |
В примере выгодно сначала ввести в строй второй станок и за оставшиеся 15 минут изготовить 45 деталей, а затем ввести в строй первый и за оставшиеся 5 минут изготовить на нём еще 20 деталей.
Если сначала ввести в строй первый станок и изготовить на нем в оставшиеся 10 минут 40 деталей, то после введения в строй второго на нем удастся изготовить лишь 15 деталей, суммарно 55, что меньше, чем 65.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
В первых четырех подзадачах достаточно легко найти конкретную формулу, которая позволяет найти ответ. Обозначим искомое количество деталей как r.
Важно не забыть, что время на запуск может оказаться больше k, и тогда количество деталей будет равно 0, для чего мы и берем max в формуле.
Тут снова надо не забыть о случаях, когда время на введение в строй больше доступного нам.
Если станки производят детали с одинаковой скоростью, то требуется ввести в строй сначала тот, на запуск которого уйдет меньше времени, чтобы детали раньше начали производиться. Получаем: r = a ⋅ max(k − min(a, b), 0) + a ⋅ max(k − a − b, 0).
Теперь посмотрим как решать общий случай. Переберем два варианта: какой станок будем вводить в строй первым. Если мы сначала введем в строй первый станок, ответ будет: 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).
Заметим, что, разумеется, решение пятой подзадачи решает также и первые четыре подзадачи.