Задание 18 ЕГЭ по информатике · D99C0C
ВысокаяКЭС 4.2КЭС 4.3
Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
Для указанных входных данных ответом является пара чисел:
18_D99C0C.xlsxПеред запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом является пара чисел:
| 27 | 41 |
|---|
| Ответ: |
|---|
Показать ответ
622 1087
Подсказки (3)
- Из каких клеток может прийти Робот в текущую клетку, если разрешены только движения вправо и вниз?
- Для каждой клетки храните две величины: минимальную и максимальную сумму бонусов на допустимом пути до неё. Переход выполняется только через границу без стены.
- Для клетки (i,j) прибавьте её бонус к минимуму или максимуму из доступных значений для клеток (i−1,j) и (i,j−1). В правой нижней клетке получатся искомые суммы.
Решение
1. Разобьём задачу на подзадачи: для каждой клетки найдём минимальную и максимальную сумму бонусов, которую можно получить при попадании в эту клетку.
2. В начальной клетке обе величины равны её бонусу. Для каждой следующей клетки рассматриваем только те клетки сверху и слева, с которыми нет стены.
3. Если bi,j — бонус клетки, то для доступных переходов вычисляем минимум и максимум среди значений соседних клеток, после чего прибавляем bi,j.
4. После обработки всей таблицы минимальная и максимальная суммы находятся в правой нижней клетке. Их записывают в указанном порядке.
2. В начальной клетке обе величины равны её бонусу. Для каждой следующей клетки рассматриваем только те клетки сверху и слева, с которыми нет стены.
3. Если bi,j — бонус клетки, то для доступных переходов вычисляем минимум и максимум среди значений соседних клеток, после чего прибавляем bi,j.
4. После обработки всей таблицы минимальная и максимальная суммы находятся в правой нижней клетке. Их записывают в указанном порядке.
Частые ошибки
- Не учитывать бонус начальной или конечной клетки.
- Переходить через границу, отмеченную утолщением.
- Использовать только один вариант пути вместо сравнения всех допустимых путей.
- Записать максимальную сумму перед минимальной.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –в соседнюю…Наибольшая и наименьшая сумма по пути · B4F84818вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · B898EB18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · D0BC8A18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · D1737A18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · D9CFB218вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · DE9F2818Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за…Наибольшая и наименьшая сумма по пути · E02E7018вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E30D28
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.