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