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

18. Исполнитель Робот: Условие

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

Условие

Квадрат разлинован на $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+44=62$,
$Q2=18+12=30$,
$R2=36+\max(62;30)=98$.

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

Для поиска минимальной суммы заменим сравнение в R2:

=ЕСЛИ(Q2<R1;Q2+B2;R1+B2)

После копирования формулы в диапазон R2:AE15 получим: $645$.

Код на Python

Сохраним исходную таблицу в формате CSV под именем 18-04.csv.

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-04.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] = mx[0][j] = mx[0][j - 1] + s[0][j]

for i in range(1, N):
    mn[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])

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

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

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