Задание 18 ЕГЭ по информатике: Робот-сборщик: сумма на пути. Тренировочная версия: данные приведены в условии, ответ — целое число.
Подсказка: Разбери условие по шагам: отдельно запиши промежуточные значения (подсчёт, суммы, остатки). Ответ — целое число.
Примеры с разбором
Пример 1
В каждой клетке таблицы 6×5 лежат монеты. Робот стартует в левом верхнем углу и может идти только вправо или вниз до правого нижнего угла, собирая монеты во всех клетках пути (включая первую и последнюю). Чему равна наибольшая возможная сумма собранных монет?
Решение: Динамика: в каждой клетке лучшая сумма = значение клетки + большая из сумм клетки сверху и клетки слева.
Пример 2
В каждой клетке таблицы 4×4 лежат монеты. Робот стартует в левом верхнем углу и может идти только вправо или вниз до правого нижнего угла, собирая монеты во всех клетках пути (включая первую и последнюю). Чему равна наименьшая возможная сумма собранных монет?
21 35 6 14
15 7 33 23
19 9 4 34
25 38 8 30
Ответ: 94
Решение: Динамика: в каждой клетке лучшая сумма = значение клетки + меньшая из сумм клетки сверху и клетки слева.
Пример 3
В каждой клетке таблицы 5×6 лежат монеты. Робот стартует в левом верхнем углу и может идти только вправо или вниз до правого нижнего угла, собирая монеты во всех клетках пути (включая первую и последнюю). Чему равна наибольшая возможная сумма собранных монет?