Поле 5 × 5, клетки заданы парами (столбец; строка), нумерация от 1 до 5. За один шаг можно перейти в соседнюю клетку по горизонтали или вертикали, по диагонали ходить нельзя. Заблокированные клетки (2;3), (3;3), (4;2) проходить нельзя, остальные клетки можно посещать сколько угодно раз. Старт и финиш находятся в клетке S = (1;1); маршрут начинается и заканчивается в S. На поле расположены четыре станции: A = (1;4) даёт 4 очка, B = (3;4) даёт 7 очков, C = (5;1) даёт 6 очков, D = (5;5) даёт 11 очков. Каждый шаг стоит 1 минуту и 1 единицу энергии. Забор груза на станции стоит ещё 1 минуту и 1 единицу энергии, очки начисляются только за забор груза, а проходить через станцию без забора груза можно. Груз на каждой станции можно забрать не более одного раза. Суммарное время маршрута, включая возвращение в S, не должно превышать 20 минут, а суммарные затраты энергии не должны превышать 18 единиц. Нужно набрать максимум очков. В ответе укажите буквы станций, с которых забран груз, в алфавитном порядке, без учёта порядка обхода.

Так как каждый шаг и каждый забор груза расходуют по одной единице энергии, для набора груза на k станциях число шагов не должно превышать \(18-k\).

Проверим наиболее выгодные варианты:

• ABC: маршрут \(S\to A\to B\to C\to S\) можно выполнить за \(4+2+5+4=15\) шагов. С учётом трёх заборов груза получаем 18 минут и 18 единиц энергии. Очки: \(4+7+6=17\).
• CD: маршрут \(S\to C\to D\to S\) занимает \(4+4+8=16\) шагов. С учётом двух заборов груза получаем 18 минут и 18 единиц энергии. Очки: \(6+11=17\).

Все четыре станции посетить с забором груза нельзя: даже кратчайший маршрут требует не менее 18 шагов, а вместе с четырьмя заборами это 22 единицы энергии. Другие допустимые наборы дают не более 16 очков.

Таким образом, максимум составляет 17 очков, и существуют два равноправных оптимальных ответа.

Ответ: ABC или CD.