Задание 18 ЕГЭ по информатике · 2E6CE7
ВысокаяКЭС 4.2КЭС 4.3
Квадрат разлинован на N × N клеток (1 < N < 26). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером
N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
Для указанных входных данных ответом является пара чисел:
18_2E6CE7.xlsxПеред запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером
N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом является пара чисел:
| 27 | 41 |
|---|
| Ответ: |
|---|
Показать ответ
467 705
Подсказки (3)
- Какую информацию о клетке нужно хранить, чтобы определить лучший маршрут до неё?
- Для каждой клетки отдельно вычислите минимальную и максимальную сумму бонусов при движении к ней из левой верхней клетки.
- Для клетки без стены используйте переходы min(i,j)=bi,j+min(min(i−1,j),min(i,j−1)) и max(i,j)=bi,j+max(max(i−1,j),max(i,j−1)), учитывая только разрешённые переходы.
Решение
1. Обозначим через mi,j минимальную, а через Mi,j максимальную сумму бонусов на пути из левой верхней клетки в клетку (i,j).
2. Начальные значения для левой верхней клетки равны её бонусу: она входит в сумму маршрута.
m1,1=M1,1=b1,1
3. Для каждой следующей клетки рассмотрим возможные переходы из клетки сверху и из клетки слева. Переход через стену исключается.
4. Минимальная сумма получается добавлением бонуса клетки к минимальной из доступных сумм, максимальная — к максимальной из доступных сумм.
mi,j=bi,j+min(p,q)→(i,j)mp,q,Mi,j=bi,j+max(p,q)→(i,j)Mp,q
5. В правой нижней клетке получаются искомые минимальная и максимальная суммы. Их записывают в указанном порядке.
2. Начальные значения для левой верхней клетки равны её бонусу: она входит в сумму маршрута.
m1,1=M1,1=b1,1
3. Для каждой следующей клетки рассмотрим возможные переходы из клетки сверху и из клетки слева. Переход через стену исключается.
4. Минимальная сумма получается добавлением бонуса клетки к минимальной из доступных сумм, максимальная — к максимальной из доступных сумм.
mi,j=bi,j+min(p,q)→(i,j)mp,q,Mi,j=bi,j+max(p,q)→(i,j)Mp,q
5. В правой нижней клетке получаются искомые минимальная и максимальная суммы. Их записывают в указанном порядке.
Частые ошибки
- Не учитывать бонус начальной или конечной клетки.
- Разрешать переход через стену.
- Использовать только один из двух вариантов пути и не сравнивать все допустимые маршруты.
- Перепутать порядок записи минимальной и максимальной сумм.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 081BA418вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 15F34718вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 1D7ADE18вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 2285C918вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 34C97E18Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · 35A50018вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю…Наибольшая и наименьшая сумма по пути · 4392F718Задание выполняется с использованием прилагаемых к заданию файлов. Квадрат разлинован на N × N клеток (1 < N…Наибольшая и наименьшая сумма по пути · 49567F
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.