Задание 18 ЕГЭ по информатике · B2DDED
ВысокаяКЭС 4.2КЭС 4.3
Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
Для указанных входных данных ответом является пара чисел:
18_B2DDED.xlsxПеред запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом является пара чисел:
| 27 | 41 |
|---|
| Ответ: |
|---|
Показать ответ
486 707
Подсказки (3)
- Для каждой клетки определите минимальную и максимальную сумму бонусов, с которой Робот может в неё попасть.
- Значения в клетке вычисляются из значений доступных соседних клеток сверху и слева с учётом бонуса текущей клетки.
- Для каждой достижимой клетки используйте формулы minSumi,j=bi,j+min(minSumi−1,j,minSumi,j−1) и maxSumi,j=bi,j+max(maxSumi−1,j,maxSumi,j−1), исключая переходы через стены.
Решение
1. Робот движется только вправо и вниз, поэтому в клетку он может попасть только из клетки сверху или из клетки слева. 2. Для каждой клетки строим два значения: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку. 3. Если переход из соседней клетки разрешён, прибавляем бонус текущей клетки к соответствующему минимуму или максимуму. Если один из переходов запрещён стеной, он не рассматривается. 4. После заполнения таблиц в правой нижней клетке получаем минимальную и максимальную суммы бонусов. Эти два значения записываются в указанном порядке.
Частые ошибки
- Не учитывают бонус начальной или конечной клетки.
- Разрешают переход через стену.
- Перепутывают порядок: сначала требуется минимальная, затем максимальная сумма.
- Учитывают только один из возможных путей.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 9E5F7718вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · A12AAD18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · AE45C918вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · AE95F018вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –в соседнюю…Наибольшая и наименьшая сумма по пути · B4F84818вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · B898EB18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · D0BC8A18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · D1737A
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.