Задание 18 ЕГЭ, информатика: Робот-сборщик монет
Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз.
Шаг вправо разрешается сделать только в клетку с числом той же чётности, шаг вниз — только в клетку с числом другой чётности. Шаг по диагонали возможен всегда.
Необходимо перевести робота в правую нижнюю клетку поля. Определите максимальную сумму чисел в клетках, через которые можно провести такой маршрут. Определите также количество клеток поля, в которые робот не сможет попасть из-за ограничений на возможные переходы.
В ответе запишите два числа: сначала максимально возможное значение суммы входящих в маршрут чисел, затем количество недоступных клеток.
Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4 × 4):
| 53 | 63 | 18 | 80 |
| 12 | 55 | 62 | 98 |
| 2 | 64 | 59 | 87 |
| 86 | 47 | 50 | 13 |
При указанных входных данных максимальное значение 250 получится при движении по маршруту 53 → 63 → 62 → 59 → 13. Недоступны для робота клетки с числами 18, 80, 2, 86 — всего 4 клетки. В ответе в данном случае надо записать
Ответ:
Ещё задачи этой подтемы
- № 27415Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ
- № 27667Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ
- № 27669Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ
- № 27671Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ
- № 27673Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ
- № 27675Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещ