Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 18. Информатика. 2022-2
- Просмотры: 1004
- Изменено: 1 февраля 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\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования