Задание 18 ЕГЭ по информатике · EAAB4F
ВысокаяКЭС 4.2КЭС 4.3
Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером
N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
Для указанных входных данных ответом является пара чисел:
18_EAAB4F.xlsxПеред запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером
N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом является пара чисел:
| 27 | 41 |
|---|
Показать ответ
485 710
Подсказки (3)
- Для каждой клетки определите лучший и худший результат, с которым Робот может в неё попасть.
- Значения в клетке вычисляются из доступных соседей сверху и слева: для минимума берётся меньшее значение, для максимума — большее.
- Инициализируйте левую верхнюю клетку её бонусом и последовательно заполните таблицы минимумов и максимумов, учитывая стены. В правой нижней клетке получатся искомые ответы.
Решение
1. Обозначим бонус клетки в строке i и столбце j через ai,j. Для каждой клетки создадим два значения: минимальную и максимальную суммы бонусов на допустимом пути от начальной клетки.
mni,j=min допустимых сумм,mxi,j=max допустимых сумм
2. В начальной клетке оба значения равны её бонусу. Если в клетку можно попасть сверху, учитываем значение из клетки над ней; если слева — из клетки слева. Переход через утолщённую границу запрещён.
mni,j=ai,j+min(mni−1,j,mni,j−1),mxi,j=ai,j+max(mxi−1,j,mxi,j−1)
3. Последовательно обрабатываем клетки слева направо и сверху вниз. В правой нижней клетке считываем минимальную и максимальную суммы.
mni,j=min допустимых сумм,mxi,j=max допустимых сумм
2. В начальной клетке оба значения равны её бонусу. Если в клетку можно попасть сверху, учитываем значение из клетки над ней; если слева — из клетки слева. Переход через утолщённую границу запрещён.
mni,j=ai,j+min(mni−1,j,mni,j−1),mxi,j=ai,j+max(mxi−1,j,mxi,j−1)
3. Последовательно обрабатываем клетки слева направо и сверху вниз. В правой нижней клетке считываем минимальную и максимальную суммы.
Частые ошибки
- Не учитывать бонус начальной или конечной клетки.
- Разрешать переход через стену.
- Искать только один из двух экстремумов.
- Считать путь с движением вверх или влево, хотя разрешены только движения вправо и вниз.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за…Наибольшая и наименьшая сумма по пути · E02E7018вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E30D2818вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E4586818вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E705C518вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · F4E6CC18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · F7EDCC18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · FAFE1B18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · FF6D0E
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.