ЕГЭОГЭ
Задание № 15 · ОГЭ

Минимальное число переливаний

Как найти кратчайшее решение задачи исполнителя «Водолей»
3 мин чтенияСложность: Обновлено 29 сентября 2026

Минимальное число переливаний — это наименьшее количество команд исполнителя «Водолей», необходимое для получения заданного объёма воды. Чтобы его найти, сравнивают возможные последовательности команд и выбирают самую короткую.

Минимальное число переливанийСлово «минимальное» означает «самое маленькое из возможных».
Наименьшее число допустимых переливаний, переводящих начальное состояние сосудов в состояние, где в одном из сосудов содержится требуемый объём воды. Переливание выполняют до полного заполнения сосуда-назначения, полного опустошения сосуда-источника или до окончания одного из этих условий.

Как считают команды

Состояние задачи задаётся объёмами воды в сосудах, например \((a,b)\). Одно переливание изменяет это состояние и считается одной командой. Сначала полезно изучить стратегию решения задачи Водолей, а затем перечислить достижимые состояния; понятие достижимости подробно рассматривается на странице достижимость объёма в задаче Водолей.

\[L=\min\{k\mid\text{после }k\text{ переливаний получен требуемый объём}\}\]

Если состояния представить вершинами, а переливания — рёбрами, минимальное число переливаний равно длине кратчайшего пути от начального состояния до подходящей вершины. Поэтому для систематического поиска применяют поиск по графу состояний: сначала проверяют состояния на расстоянии 1, затем на расстоянии 2 и так далее.

№
Пример

Есть сосуды на 5 и 3 литра, оба изначально пусты. Нужно получить 4 литра. Кратчайшая последовательность: наполнить 5-литровый сосуд; перелить из него в 3-литровый; вылить 3-литровый сосуд; снова перелить оставшиеся 2 литра в 3-литровый; снова наполнить 5-литровый сосуд; долить 3-литровый сосуд до полного. В 5-литровом сосуде останется 4 литра. Ответ: 6 переливаний.

!
Не перепутайте

Минимальное число переливаний не равно числу промежуточных состояний. Если путь содержит 6 команд, то между начальным и конечным состояниями может быть 5 промежуточных состояний. Также нельзя считать переливанием наполнение или опустошение сосуда, если по условию это отдельные команды: всегда учитывайте точные правила исполнителя.

Проверьте себя

Что означает ответ 4 в задаче о Водолее?

Главное за минуту

Главное

  • Минимальное число переливаний — длина самой короткой допустимой последовательности команд.
  • Каждое переливание считается одной командой, а состояние описывается объёмами воды в сосудах.
  • Для гарантированного поиска минимума удобно использовать поиск по уровням графа состояний.