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