Ведра с водой (Water Pails)
Предположим, у вас есть всего два ведра объёмами
x и y. Ваша задача — набрать суммарное количество воды в этих ведрах, максимально близкое к целевому количеству s.Вам разрешено выполнить не более
k операций из следующего списка:- Наполнить одно из ведер доверху.
- Опорожнить одно из ведер.
- Перелить воду из одного ведра в другое, останавливаясь, когда второе ведро заполнится или первое опустеет (что наступит раньше).
Изначально оба ведра пусты.
Возможно, достичь ровно
s в сумме не получится, поэтому нужно найти минимальную разницу |s - s’|, где s’ — это общее количество воды в двух ведрах.Входные данные
В единственной строке входных данных заданы 4 целых числа:
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) и s (1 ≤ s ≤ 200).Выходные данные
Программа должна вывести наименьшую абсолютную разницу, которую можно получить, выполнив не более
k операций.Примеры
Input | Output |
14 50 2 32 | 18 |
Пояснение
Разрешено выполнить только 2 операции. Ниже перечислены все результаты, достигнутые за 2 шага:
- (0, 0) → 0 единиц
- (14, 0) → 14 единиц
- (0, 50) → 50 единиц
- (0, 14) → 14 единиц
- (14, 36) → 50 единиц
- (14, 50) → 64 единиц
Таким образом, ближе всего к 32 получается 14, и разница составляет 18.
Заметим, что мы могли бы получить 36, опустошив первое ведро из состояния (14, 36), но это заняло бы уже 3 шага, а нам разрешено не более 2.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB