Задание 18 ЕГЭ по информатике · 6303B2
ВысокаяКЭС 4.5
Задание выполняется с использованием прилагаемых файлов.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
307_18_6303B2.xlsxКвадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Показать ответ
2404 481
Подсказки (3)
- Для каждой клетки определите максимальную и минимальную сумму, с которыми Робот может попасть в неё из левой верхней клетки.
- При переходе в клетку учитывайте только разрешённые переходы сверху и слева; для максимума выбирайте большее значение, для минимума — меньшее.
- Продолжайте динамический расчёт до всех клеток, у которых справа и снизу стоят стены. Среди значений в этих конечных клетках выберите глобальные максимум и минимум.
Решение
1. Считаем для каждой клетки две величины: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку. Начальная клетка получает значение, равное номиналу монеты в ней.
M1,1=m1,1,L1,1=m1,1
2. Для каждой клетки рассматриваем только те клетки, из которых в неё можно перейти: верхнюю, если между клетками нет горизонтальной стены, и левую, если между клетками нет вертикальной стены.
Mi,j=mi,j+max(k,l)→(i,j)Mk,l,Li,j=mi,j+min(k,l)→(i,j)Lk,l
3. Для всех клеток, ограниченных стенами справа и снизу, сравниваем рассчитанные значения. Максимальный итог — наибольшее значение M, минимальный итог — наименьшее значение L.
4. Числовой ответ нельзя вычислить по представленному условию: содержимое прилагаемой электронной таблицы с реальными номиналами монет и стенами отсутствует. Приведённая в условии таблица является только примером входных данных.
M1,1=m1,1,L1,1=m1,1
2. Для каждой клетки рассматриваем только те клетки, из которых в неё можно перейти: верхнюю, если между клетками нет горизонтальной стены, и левую, если между клетками нет вертикальной стены.
Mi,j=mi,j+max(k,l)→(i,j)Mk,l,Li,j=mi,j+min(k,l)→(i,j)Lk,l
3. Для всех клеток, ограниченных стенами справа и снизу, сравниваем рассчитанные значения. Максимальный итог — наибольшее значение M, минимальный итог — наименьшее значение L.
4. Числовой ответ нельзя вычислить по представленному условию: содержимое прилагаемой электронной таблицы с реальными номиналами монет и стенами отсутствует. Приведённая в условии таблица является только примером входных данных.
Частые ошибки
- Не учитывать монету в начальной или конечной клетке.
- Разрешать переход через внутреннюю стену.
- Рассматривать только правую нижнюю клетку и игнорировать другие конечные клетки.
- Искать максимум и минимум только среди маршрутов одинаковой длины.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · 49567F18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 49E2DA18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 4B5A0B18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 55978C18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · 6999A718вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –в соседнюю…Наибольшая и наименьшая сумма по пути · 72C25218вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 776E3618вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз –в соседнюю…Наибольшая и наименьшая сумма по пути · 779E0A
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.