Робот идёт вправо и вниз по полю с монетами и стенами. Нужно найти наибольшую и наименьшую сумму, которую он может собрать к концу маршрута. К каждому варианту — файл .xlsx, стены отмечены толстыми границами.
Идея динамики
Сумма в клетке = монета + лучшая сумма из соседа слева или сверху.
Стена между клетками — соседа не учитываем.
Ответ — по конечным клеткам (стена справа и снизу).
В Excel
Копия поля справа, формула =МАКС(слева; сверху) + монета.
У стен — ссылка только на доступного соседа.
Минимум — вторая копия с МИН.
Типичные ошибки
Не учесть конечные клетки внутри поля — только правый нижний угол.
Протянуть формулу «сквозь» стену.
Забыть монету в начальной клетке.
Разобранные варианты
Сначала реши сам в Excel или на Python, потом открой разбор.
Вариант 1
поле 10×10 · концов 6
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): F2, F5, F8, H8, J8, F10. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 912 и 251.
Ответ: 912 251
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v1.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 2
поле 11×11 · концов 3
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): E5, G5, K11. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1255 и 364.
Ответ: 1255 364
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v2.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 3
поле 12×12 · концов 4
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): J8, G10, G12, L12. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1364 и 474.
Ответ: 1364 474
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v3.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 4
поле 14×14 · концов 4
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): G6, H11, D14, N14. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1483 и 394.
Ответ: 1483 394
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v4.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 5
поле 15×15 · концов 3
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): J3, O13, O15. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 2006 и 537.
Ответ: 2006 537
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v5.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 6
поле 15×15 · концов 5
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): O2, O11, B15, H15, O15. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 2026 и 595.
Ответ: 2026 595
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v6.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 7
поле 11×11 · концов 3
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): H6, C11, K11. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1574 и 661.
Ответ: 1574 661
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v7.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 8
поле 15×15 · концов 4
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): C6, I6, C9, O15. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1721 и 358.
Ответ: 1721 358
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v8.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 9
поле 13×13 · концов 6
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): K3, B7, D7, G7, H10, M13. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1629 и 385.
Ответ: 1629 385
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v9.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Вариант 10
поле 15×15 · концов 2
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Идея. Для каждой клетки считаем наибольшую (и отдельно наименьшую) сумму, с которой Робот может в неё прийти. В клетку можно прийти только слева или сверху, если там нет стены. Поэтому сумма в клетке = монета + max (или min) из сумм соседних клеток слева и сверху.
В электронной таблице. Справа от поля строим копию: в первой клетке — значение монеты, в первой строке =ячейка_слева + монета, в первом столбце =ячейка_сверху + монета, в остальных =МАКС(слева; сверху) + монета. Там, где стена отделяет клетку от соседа, формулу правим вручную: берём только доступного соседа. Затем копию повторяем с МИН.
Конечные клетки (стена справа и снизу, достижимы из начала): F15, O15. Ответ — максимум и минимум посчитанных сумм по этим клеткам: 1800 и 705.
Ответ: 1800 705
Решение на Python. Положите файл рядом с программой (нужна openpyxl). Стены программа находит по стилю границы ячеек: утолщённая граница — 'medium'.
from openpyxl import load_workbook
ws = load_workbook('Ege18_v10.xlsx').active
n = ws.max_row
coin = [[ws.cell(r + 1, c + 1).value for c in range(n)] for r in range(n)]
def wall_right(r, c): # утолщённая граница справа у клетки или слева у соседней
return c == n - 1 or ws.cell(r + 1, c + 1).border.right.style == 'medium' \
or ws.cell(r + 1, c + 2).border.left.style == 'medium'
def wall_down(r, c):
return r == n - 1 or ws.cell(r + 1, c + 1).border.bottom.style == 'medium' \
or ws.cell(r + 2, c + 1).border.top.style == 'medium'
# mx[r][c], mn[r][c] — наибольшая и наименьшая сумма на пути из левого верхнего угла в клетку (r, c)
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if r == 0 and c == 0:
mx[r][c] = mn[r][c] = coin[0][0]
continue
prev = []
if c > 0 and not wall_right(r, c - 1) and mx[r][c - 1] is not None:
prev.append((mx[r][c - 1], mn[r][c - 1]))
if r > 0 and not wall_down(r - 1, c) and mx[r - 1][c] is not None:
prev.append((mx[r - 1][c], mn[r - 1][c]))
if prev:
mx[r][c] = max(p[0] for p in prev) + coin[r][c]
mn[r][c] = min(p[1] for p in prev) + coin[r][c]
# конечные клетки: достижимы, а справа и снизу — стены
ends = [(r, c) for r in range(n) for c in range(n) if mx[r][c] is not None and wall_right(r, c) and wall_down(r, c)]
print(max(mx[r][c] for r, c in ends), min(mn[r][c] for r, c in ends))
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
поле 11×11 · концов 3
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Исходные данные — электронная таблица N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.