Робот на клетчатом поле
Робот идёт по клеткам квадрата только вправо или вниз, и лучшую сумму монет в каждой клетке находят по лучшим суммам соседей сверху и слева. Таблицу таких сумм заполняют одной формулой с копированием в электронной таблице или двойным циклом на Python. Стена убирает одного из соседей, а если конечных клеток несколько, ответ ищут среди всех клеток, закрытых справа и снизу.
Таблица лучших сумм
В клетку можно прийти только сверху или слева. Поэтому лучшая сумма в клетке — лучшая из сумм соседей сверху и слева плюс монета самой клетки.
- Начальная клетка: сумма равна её монете. Первая строка и первый столбец: у клетки один сосед.
- Остальные клетки: для наибольшей суммы, — для наименьшей.
- Стена между клетками убирает этого соседа из формулы. Клетка, в которую не войти ни сверху, ни слева, остаётся пустой.
- Ответ — значение в конечной клетке. Если конечных клеток несколько, возьмите наибольшее (наименьшее) значение среди всех клеток, закрытых справа и снизу.
- Порядок чисел в ответе берите из условия: сначала максимум или сначала минимум.
Динамическое программирование
Из левой верхней клетки квадрата в правую нижнюю ведёт маршрутов: Робот делает шагов вправо и шагов вниз в любом порядке. При это 35 345 263 800 маршрутов, перебрать их нельзя.
Динамическое программирование — метод, при котором задачу решают через ответы для меньших частей и сохраняют эти ответы в таблице. Каждую клетку считают один раз по уже готовым значениям соседей. Для поля это простых вычислений.
Пример
Сколько маршрутов ведёт из левой верхней клетки поля в правую нижнюю, если Робот ходит только вправо и вниз?
- 1.В клетку первой строки или первого столбца ведёт один маршрут: Робот идёт по прямой.
- 2.В любую другую клетку приходят сверху или слева, поэтому число маршрутов равно сумме чисел соседей сверху и слева.
- 3.Вторая строка: 1, , . Третья строка: 1, , .
- 4.Проверка по формуле: .
Ответ: 6
Наибольшая и наименьшая сумма монет
Пусть — монета клетки, а — наибольшая сумма, которую Робот может собрать на пути от старта до этой клетки включительно. В клетку приходят только сверху или слева, поэтому лучший путь в неё продолжает лучший путь в одного из этих соседей: . В начальной клетке . В первой строке сосед только слева, в первом столбце — только сверху.
Таблицу заполняют по строкам слева направо: к каждой клетке оба соседа уже посчитаны. Наименьшую сумму ищут отдельной таблицей той же формой, с вместо . Брать в одну таблицу максимум и минимум нельзя: путь с наибольшей суммой в клетку и путь с наименьшей — разные пути.
Пример
Поле , монеты по строкам: 1, 8, 8, 4; 10, 1, 1, 3; 1, 3, 12, 2; 2, 3, 5, 6. Робот идёт из левой верхней клетки в правую нижнюю. Найдите наибольшую и наименьшую сумму.
- 1.Первая строка (одинакова для обеих таблиц): 1, 9, 17, 21. Первый столбец: 1, 11, 12, 14.
- 2.Таблица наибольших сумм, строки 2–4: 11, , 18, 24; 12, 15, 30, 32; 14, 18, 35, 41.
- 3.Таблица наименьших сумм, строки 2–4: 11, , 11, 14; 12, 13, 23, 16; 14, 16, 21, 22.
- 4.В правой нижней клетке: 41 и 22.
Ответ: 41 и 22
Таблица сумм в Excel и LibreOffice Calc
Пусть поле занимает ячейки A1:J10. Таблицу сумм стройте справа, например в L1:U10, на том же месте каждой клетки. В L1 напишите =A1. В M1 — =L1+B1 и скопируйте вправо до U1: первая строка. В L2 — =L1+A2 и скопируйте вниз до L10: первый столбец. В M2 — =МАКС(L2;M1)+B2 и скопируйте на весь прямоугольник M2:U10. Ссылки относительные, поэтому в каждой ячейке формула берёт своих соседей сверху и слева и свою монету: относительные ссылки.
Ответ стоит в правой нижней ячейке U10. Для наименьшей суммы постройте вторую таблицу так же, с МИН вместо МАКС.
Пример задания
Открытый банк ФИПИ
Квадрат разлинован на N × N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел:
| 41 | 22 |
Стены между клетками
Стена в файле нарисована толстой линией между ячейками. Сквозь неё Робот не проходит, поэтому сосед за стеной выпадает из формулы. Стена справа от клетки X убирает соседа слева у клетки справа от X. Стена под клеткой X убирает соседа сверху у клетки под X. Где сосед остался один, формула берёт только его. Пусть у клетки D2 стена слева: тогда в её ячейке таблицы сумм O2 пишут =O1+D2 вместо =МАКС(N2;O1)+D2.
Если клетку закрывают стены и сверху, и слева, или единственный сосед сам недостижим, Робот в неё не попадает: такую ячейку таблицы сумм оставьте пустой. Пройдите по всем стенам поля и исправьте формулы рядом с каждой.
Пример
Поле из предыдущего примера, клетки A1:D4. Стены: справа от C2, под C2, под A3. Найдите наибольшую и наименьшую сумму в правой нижней клетке D4.
- 1.D2: стена слева, сумма только сверху: в обеих таблицах.
- 2.C3: стена сверху, сумма только слева. A4: стена сверху и нет соседа слева, клетка недостижима. B4: только сверху.
- 3.Наибольшие суммы, строки 3–4: 12, 15, , 29; пусто, 18, 32, 38.
- 4.Наименьшие суммы, строки 2–4: 11, 10, 11, 24; 12, 13, 25, 26; пусто, 16, 21, 27.
Ответ: 38 и 27
Двумерный массив в Python
Двумерный массив (матрица) — таблица чисел из строк и столбцов. В Python это список строк, каждая строка — список чисел: a[r][c] — число в строке r и столбце c, нумерация с нуля. len(a) — число строк, len(a[0]) — число столбцов. Таблицу из файла CSV читают так: a = [[int(x) for x in line.split(';')] for line in open('18.csv')].
Сумма строки r — sum(a[r]). Сумма столбца c — sum(a[r][c] for r in range(n)). Главная диагональ — клетки a[i][i]. Наибольшее число — max(max(row) for row in a). Строки меняют местами одной строкой a[0], a[2] = a[2], a[0]. Пустую таблицу создают так: [[0] * n for _ in range(n)].
Пример
Матрица по строкам: 3, 8, 1; 5, 2, 7; 4, 6, 9. Найдите сумму второй строки, сумму третьего столбца, сумму главной диагонали и наибольшее число, затем поменяйте местами первую и третью строки.
- 1.Вторая строка —
a[1]: . - 2.Третий столбец —
a[r][2]: . - 3.Диагональ —
a[0][0],a[1][1],a[2][2]: . Наибольшее число 9. - 4.После обмена первая строка 4, 6, 9, третья 3, 8, 1.
Ответ: 14, 17, 14, 9; строки 4, 6, 9 / 5, 2, 7 / 3, 8, 1
Несколько конечных клеток
В части заданий Робот останавливается в любой клетке, которую ограничивают стены или край поля и справа, и снизу: дальше ему идти некуда. Такая клетка бывает и внутри поля. Постройте таблицы сумм как обычно, затем выпишите значения во всех таких клетках, до которых Робот может дойти. Ответ — наибольшее из значений таблицы максимумов и наименьшее из значений таблицы минимумов.
В поле с тремя стенами из примера выше конечные клетки — C2 (стены справа и снизу) и D4. Наибольшие суммы в них 18 и 38, наименьшие 11 и 27. Ответ: 38 и 11.
Программа на Python
Программа заполняет таблицу сумм d двойным циклом по строкам и столбцам. Стены записывают вручную двумя множествами клеток: right — клетки со стеной справа, down — клетки со стеной снизу; клетка — пара (строка, столбец) с нумерацией с нуля. Сосед слева годится, если у него нет стены справа и он достижим (d не None); сосед сверху — если у него нет стены снизу. Функция solve получает max или min и возвращает лучшее значение среди конечных клеток.
Программа ниже считает поле с тремя стенами из примеров выше и печатает 38 11. Для поля без стен множества пусты, и конечная клетка одна — правая нижняя.
Пример задания
Открытый банк ФИПИ
Задание выполняется с использованием прилагаемых файлов.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных
