Задание 18 ЕГЭ по информатике · D9CFB2
ВысокаяКЭС 4.5
Задание выполняется с использованием прилагаемых файлов.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
1_18_D9cFB2.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 |
Показать ответ
2009 628
Подсказки (3)
- Для каждой клетки определите, из каких клеток в неё можно прийти: сверху и слева.
- Для максимальной суммы храните в клетке максимум из достижимых сумм, а для минимальной — минимум. Переход возможен только при отсутствии стены.
- Начальное значение равно стоимости монеты в левой верхней клетке. В каждой конечной клетке сравните найденные максимальную и минимальную суммы со значениями в остальных конечных клетках.
Решение
1. Считаем стоимость монеты в каждой клетке и сведения о стенах из приложенной электронной таблицы.
2. Для каждой клетки вычисляем две величины: максимальную и минимальную сумму, которую можно набрать при попадании в эту клетку. Переходы выполняются только вправо и вниз и только через проходы без стен.
Mi,j=ai,j+max(Mi−1,j,Mi,j−1)
3. Аналогично вычисляем минимальную сумму, заменяя максимум минимумом.
mi,j=ai,j+min(mi−1,j,mi,j−1)
4. Для всех клеток, ограниченных стенами справа и снизу, выбираем наибольшее значение из таблицы максимумов и наименьшее значение из таблицы минимумов.
Smax=max(i,j)∈FMi,j,Smin=min(i,j)∈Fmi,j
2. Для каждой клетки вычисляем две величины: максимальную и минимальную сумму, которую можно набрать при попадании в эту клетку. Переходы выполняются только вправо и вниз и только через проходы без стен.
Mi,j=ai,j+max(Mi−1,j,Mi,j−1)
3. Аналогично вычисляем минимальную сумму, заменяя максимум минимумом.
mi,j=ai,j+min(mi−1,j,mi,j−1)
4. Для всех клеток, ограниченных стенами справа и снизу, выбираем наибольшее значение из таблицы максимумов и наименьшее значение из таблицы минимумов.
Smax=max(i,j)∈FMi,j,Smin=min(i,j)∈Fmi,j
Частые ошибки
- Не учитывают монету в начальной клетке.
- Не учитывают монету в конечной клетке.
- Разрешают переход через внутреннюю стену.
- Ищут максимум и минимум только для правой нижней клетки, не проверяя остальные конечные клетки.
- Путают максимальную и минимальную суммы в итоговом ответе.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · B898EB18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · D0BC8A18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · D1737A18Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за…Наибольшая и наименьшая сумма по пути · D99C0C18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · DE9F2818Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за…Наибольшая и наименьшая сумма по пути · E02E7018вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E30D2818вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · E45868
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.