Примеры решений — №18

Условие

Квадрат разлинован на 20 × 20 клеток. В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот стартует из правой нижней клетки и за одно перемещение может выполнить одну из трёх команд:

влево — переместиться в соседнюю клетку слева;
вверх — переместиться в соседнюю клетку сверху;
влево-вверх — переместиться по диагонали в соседнюю клетку слева-сверху.

Внутренних стен в квадрате нет. Робот заканчивает движение в левой верхней клетке, из которой уже невозможно двигаться ни влево, ни вверх. Посетив клетку (включая начальную и конечную), Робот забирает монету.
Определите среднее арифметическое между минимальной и максимальной суммами монет среди всех возможных маршрутов Робота. В ответе запишите только целое число.
Исходные данные: электронная таблица 20 × 20 в прилагаемом файле. Строки пронумерованы сверху вниз (1–20), столбцы — слева направо (1–20).

18_1819.ods

Решение

Решение методом динамического программирования.

Обозначим клетки: строка r (0=верхняя, 19=нижняя), столбец c (0=левый, 19=правый). Робот стартует из (19,19) и заканчивает в (0,0).

Определим dp_max[r][c] = максимальная сумма на пути из (r,c) в (0,0),
dp_min[r][c] = минимальная сумма.

Переходы (из клетки (r,c) Робот идёт в одну из трёх):
• влево: (r, c-1) — только если c > 0
• вверх: (r-1, c) — только если r > 0
• влево-вверх: (r-1,c-1) — только если r > 0 и c > 0

Граничные случаи:
• dp[0][0] = grid[0][0] = 80
• dp[0][c] = grid[0][c] + dp[0][c-1] (строка 0 — только влево)
• dp[r][0] = grid[r][0] + dp[r-1][0] (столбец 0 — только вверх)

Результаты:
Максимальная сумма: dp_max[19][19] = 2720
Минимальная сумма: dp_min[19][19] = 928

Маршрут с максимальной суммой (ключевые клетки):
(19,19)→(18,19)→(18,18)→(18,17)→(18,16)→(17,16)→(16,16)→(15,16)→(14,16)→(14,15)
→(13,15)→(12,15)→(11,15)→(10,15)→(9,15)→(9,14)→...→(9,9)→(8,9)→(7,9)→(7,8)
→(7,7)→(6,7)→(6,6)→(6,5)→(5,5)→(5,4)→(5,3)→(5,2)→(5,1)→(4,1)→(3,1)→(2,1)
→(1,1)→(1,0)→(0,0). Сумма = 2720.

Маршрут с минимальной суммой (преимущественно диагональные ходы):
(19,19)→(18,18)→(17,17)→(16,17)→(15,17)→(14,17)→(13,16)→(12,16)→(11,16)
→(10,16)→(9,16)→(8,16)→(7,16)→(6,15)→(5,14)→(4,13)→(4,12)→(4,11)→(4,10)
→(3,9)→(3,8)→(2,7)→(1,6)→(1,5)→(1,4)→(1,3)→(0,2)→(0,1)→(0,0). Сумма = 928.

Среднее арифметическое: (2720 + 928) / 2 = 3648 / 2 = 1824.

Ответ: 1824.

Ответ:1824

#1820

Условие

Квадрат разлинован на 5 × 5 клеток. В каждой клетке лежит монета (таблица ниже, строки сверху вниз, столбцы слева направо):

10	25	30	15	20
40	15	45	20	35
20	50	25	40	15
35	20	55	30	25
15	45	20	60	50

Исполнитель Робот стартует из левой верхней клетки. За одно перемещение он может перейти в соседнюю клетку вправо или вниз. Робот заканчивает движение в правой нижней клетке. Посетив клетку (включая начальную и конечную), Робот забирает монету.

1) Найдите максимальную сумму монет на маршруте Робота.
2) Найдите количество клеток с монетой строго больше 30 на оптимальном маршруте.

В ответе запишите два числа через пробел.

Решение

grid = [[10,25,30,15,20],[40,15,45,20,35],
        [20,50,25,40,15],[35,20,55,30,25],
        [15,45,20,60,50]]
n = 5
dp = [[0]*n for _ in range(n)]
dp[0][0] = grid[0][0]
for j in range(1,n): dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1,n): dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,n):
    for j in range(1,n):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
print(dp[4][4])  # 340
# Восстановление пути
i, j = 4, 4; path = [(4,4)]
while i or j:
    if i==0: j-=1
    elif j==0: i-=1
    elif dp[i-1][j]>=dp[i][j-1]: i-=1
    else: j-=1
    path.append((i,j))
path.reverse()
# Путь: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)→(3,2)→(3,3)→(4,3)→(4,4)
# Монеты: 10,40,20,50,25,55,30,60,50 → сумма=340
count = sum(1 for r,c in path if grid[r][c]>30)
print(count)  # 5

Оптимальный путь содержит монеты: 10, 40, 20, 50, 25, 55, 30, 60, 50.
Сумма = 340; клеток с монетой > 30: 5 (40, 50, 55, 60, 50).

Ответ:340 5

№18 — примеры решений