Команды исполнителя Водолей
Исполнитель Водолей работает с сосудами заданной вместимости и выполняет команды переливания. Чтобы решить задачу, нужно точно понимать, как изменяются объёмы воды после каждой команды, а затем подобрать последовательность действий, приводящую к требуемому результату.
Водолей — исполнитель, который умеет выполнять операции с несколькими сосудами: наполнять сосуд, выливать из него воду и переливать воду из одного сосуда в другой. Вместимость сосудов постоянна, а вода не исчезает при переливании между сосудами.
Обычно сосуды обозначают буквами \(A\), \(B\), \(C\) или номерами. Для каждого сосуда известна его вместимость: например, \(a\) литров для сосуда \(A\) и \(b\) литров для сосуда \(B\). Текущее состояние удобно записывать парой или тройкой чисел. Например, \((2,5)\) означает, что в сосуде \(A\) находится 2 литра, а в сосуде \(B\) — 5 литров. Это связано с понятием состояния сосудов, которое используется при построении решения.
Команды исполнителя
Набор команд может немного отличаться в формулировках заданий, но смысл операций одинаков. Перед выполнением команды проверьте, какой сосуд является источником, а какой — приёмником.
| Команда | Действие | Результат |
|---|---|---|
| Наполнить \(A\) | Налить воду в \(A\) до полного состояния | Объём в \(A\) становится равен \(a\) |
| Опорожнить \(A\) | Вылить всю воду из \(A\) | Объём в \(A\) становится равен \(0\) |
| Перелить из \(A\) в \(B\) | Переливать до опустошения \(A\) или заполнения \(B\) | Одна из границ достигается первой |
| Перелить из \(B\) в \(A\) | То же в обратном направлении | Изменяются объёмы обоих сосудов |
При переливании из сосуда \(A\) вместимости \(a\) в сосуд \(B\) вместимости \(b\) сначала определяется свободное место в \(B\): \(b-y\), где \(y\) — текущий объём воды в \(B\). Переливаемый объём равен меньшему из количества воды в \(A\) и свободного места в \(B\).
Если перед командой состояние равно \((x,y)\), то после переливания из \(A\) в \(B\) состояние станет \((x-q,y+q)\). Здесь \(x\) и \(y\) — текущие объёмы воды. Если \(A\) опустел, значит \(q=x\); если \(B\) заполнился, значит \(q=b-y\).
Как читать условие и записывать состояние
В начале задачи нужно выписать вместимость каждого сосуда и начальные объёмы. Если сосуды пусты, начальное состояние для двух сосудов — \((0,0)\). Если разрешены только две ёмкости, достаточно двух чисел. При трёх сосудах записывают \((x,y,z)\).
- Запишите вместимости сосудов, например \(A=3\) л и \(B=5\) л.
- Запишите начальное состояние: чаще всего \((0,0)\).
- Перечислите разрешённые команды: наполнить, опорожнить, перелить.
- После каждой команды вычислите новое состояние, не пропуская промежуточные объёмы.
- Остановитесь, когда требуемый объём появился в одном из сосудов или достигнуто указанное состояние.
Есть сосуды \(A=3\) л и \(B=5\) л. Оба сосуда пусты. Требуется получить ровно 4 литра воды в сосуде \(B\).
Получена последовательность из шести команд. В конечном состоянии \((3,4)\) в сосуде \(B\) находится требуемый объём 4 литра. Важно: при последнем переливании нельзя вылить все 5 литров из \(B\), потому что сосуд \(A\) принимает только 1 литр.
Сосуды \(A=4\) л и \(B=7\) л находятся в состоянии \((3,5)\). Что получится после переливания из \(A\) в \(B\)?
Ограничения и достижимость объёма
Не любой объём можно получить при любых вместимостях сосудов. Если разрешены только переливания, наполнение и опорожнение, достижимость определяется вместимостями сосудов и их общей доступной водой. Подробно это рассматривается на странице достижимость объёма в задаче Водолей.
Для сосудов вместимостей \(a\) и \(b\) при наличии достаточного запаса воды можно получить объём \(d\) тогда и только тогда, когда \(d\le\max(a,b)\) и \(d\) кратен \(\gcd(a,b)\). Для получения ровно \(d\) литров в одном сосуде также требуется, чтобы \(d\) не превышал его вместимость.
Например, для сосудов 6 и 10 литров общий наибольший общий делитель равен 2. Поэтому объёмы 2, 4, 6, 8 и 10 достижимы, а 3 литра — нет. Однако в конкретном задании могут быть дополнительные ограничения: ограниченное количество воды, запрет на некоторые команды или требование получить объём в определённом сосуде.
Сначала попробуйте получить остатки после переливаний: разности вместимостей, затем повторяющиеся остатки. Если решение не находится вручную, перечисляйте состояния и переходы между ними. Такой подход приводит к графу состояний, а поиск кратчайшей последовательности удобно выполнять методом поиска в ширину.
Алгоритм и запись команд
Последовательность команд — это алгоритм для исполнителя. Команды должны идти в правильном порядке и быть однозначными: «перелить из \(A\) в \(B\)», а не просто «перелить». Если решение записывается в алгоритмическом языке, повторяющиеся действия можно оформить с помощью цикла, а выбор действия по условию — с помощью условия.
- У каждой команды указаны источник и приёмник.
- После каждого шага объём не отрицателен и не превышает вместимость сосуда.
- При переливании сохранён общий объём воды, если вода не наливается и не выливается.
- Финальное состояние действительно содержит требуемый объём.
- Число команд соответствует требованию задания, если оно задано.
1. Переливают воду до полного опустошения источника, хотя приёмник заполняется раньше. 2. Забывают, что команда «наполнить» доводит сосуд до его полной вместимости. 3. Путают направление переливания: \(A\to B\) и \(B\to A\) дают разные результаты. 4. Записывают только объём в одном сосуде и теряют информацию о другом. 5. Считают достижимым любой целый объём, не проверив делимость на \(\gcd(a,b)\). 6. Останавливаются после появления нужного объёма, хотя условие требует, чтобы он находился в конкретном сосуде.
Для тренировки после этой страницы полезно перейти к стратегии решения задачи Водолей и затем к решению методом переливаний. Если требуется формальная запись алгоритма с данными, рядом пригодятся страницы о переменной и командах других исполнителей, например командах исполнителя Кузнечик.
Быстрая проверка
Проверьте понимание
Главное
- Водолей выполняет команды наполнения, опорожнения и переливания между сосудами.
- При переливании вода движется до опустошения источника или заполнения приёмника.
- Состояние записывают объёмами воды во всех сосудах; после каждой команды состояние изменяется.
- Для двух сосудов достижимые объёмы связаны с \(\gcd\) их вместимостей.
- Решение проверяют пошаговой таблицей состояний, а сложные варианты можно представить графом и искать по нему кратчайший путь.