Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

18. Исполнитель Робот: Квадрат разлинован на N× N клеток (1<N<26)

Задание #297193
Решено верно
Решено неверно
Сообщить о проблеме

Квадрат разлинован на $N\times N$ клеток ($1<N<26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.

Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее $100$. Это правило относится к начальной и конечной клеткам маршрута Робота.

Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.

Исходные данные представлены в форме электронной таблицы размером $N\times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

Пример входных данных:

Для указанных входных данных ответом является пара чисел: $27$ $41$.

В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$. Внутренних стен нет. В каждую клетку Робот может попасть либо слева, либо сверху. Числа исходной таблицы представлены в приложенном файле.

Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.

В ячейку Q1 запишем: =СУММ($A$1:A1)

Скопируем формулу в диапазоны R1:AE1 и Q2:Q15.

Для поиска максимальной суммы в ячейку R2 запишем: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток:

$Q1=18$,
$R1=18+23=41$,
$Q2=18+13=31$,
$R2=27+\max(41;31)=68$.

В ячейке AE15 получим максимальную сумму: $707$.

Для поиска минимальной суммы в R2 запишем: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

Скопируем формулу в диапазон R2:AE15.

Для первых клеток: $R2=27+\min(41;31)=58$.

В ячейке AE15 получим минимальную сумму: $486$.

Код на Python

Если сохранить исходную таблицу в формате CSV с именем 18-09.csv:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-09.csv').read().splitlines()
)

N = len(s)

mn = [[0] * N for _ in range(N)]
mx = [[0] * N for _ in range(N)]

mn[0][0] = mx[0][0] = s[0][0]

for j in range(1, N):
    mn[0][j] = mn[0][j - 1] + s[0][j]
    mx[0][j] = mx[0][j - 1] + s[0][j]

for i in range(1, N):
    mn[i][0] = mn[i - 1][0] + s[i][0]
    mx[i][0] = mx[i - 1][0] + s[i][0]

for i in range(1, N):
    for j in range(1, N):
        mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
        mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])

print(mn[-1][-1], mx[-1][-1])

Программа выводит:

486 707
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение