Информатика. ЕГЭ
Задание 18. Информатика. 2022-2
- Просмотры: 977
- Изменено: 2 февраля 2025
Квадрат разлинован на \(N \times N\) клеток \( ( 1 < N < 20)\). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, а по команде вниз — в соседнюю нижнюю. При попытке пересечь границы (внутренние и границы квадрата) Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от \(1\) до \(100\). Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером \( N \times N\), каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
| 1 | 5 | 8 | 4 |
| 10 | 1 | 10 | 3 |
| 1 | 3 | 1 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел:
| 36 | 24 |
Решение:
На экзамене рекомендуется решать это задание с помощью табличного процессора.
Python
Границы необходимо вручную добавить в кортеж кортежей boundary. Каждый кортеж внутри boundary имеет вид \( (m , \,\, n) \), где \( m \) — номер ячейки с границей, а \( n \) — номер ячейки, из которой нельзя попасть в ячейку с номером \( m \). Например, \( ( 14, \,\, 10 ) \) означает, что в ячейку с номером \( 14 \) нельзя попасть из ячейки с номером \( 10 \).
from math import sqrt
# table = [1, 5, 8, 4, 10, 1, 10, 3, 1, 3, 1, 2, 2, 3, 5, 6]
# boundary = ((10,9),)
table = []
f = open('18var2.csv')
s = f.readline()
while s:
table += list(map(int, s.split(',')))
s = f.readline()
boundary=((43, 42), (63, 62), (83, 82), (103, 102), (123, 122), \
(226, 225), (246, 245), (266, 265), (286, 285))
N = int(sqrt(len(table)))
table_min = [0] * (N ** 2)
table_max = [0] * (N ** 2)
table_min[0] = table[0]
table_max[0] = table[0]
for i in range(1, N):
table_min[i] = table_min[i-1] + table[i]
table_max[i] = table_max[i-1] + table[i]
table_min[i*N] = table_min[(i-1)*N] + table[i*N]
table_max[i*N] = table_max[(i-1)*N] + table[i*N]
for i in range(1, N):
for k in range(1, N):
v_vert = table_min[(k-1)*N+i] + table[k*N+i] if (k*N+i, (k-1)*N+i) not in boundary else 1000000
v_hor = table_min[k*N+i-1] + table[k*N+i] if (k*N+i, k*N+i-1) not in boundary else 1000000
table_min[k*N + i] = min(v_vert, v_hor)
v_vert = table_max[(k-1)*N+i] + table[k*N+i] if (k*N+i, (k-1)*N+i) not in boundary else -1000000
v_hor = table_max[k*N+i-1] + table[k*N+i] if (k*N+i, k*N+i-1) not in boundary else -1000000
table_max[k*N + i] = max(v_vert, v_hor)
print(table_max[-1], table_min[-1])
Ответ: \(721\) \(559\)
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года