Задание № 4 О баллов Уровень ЕГЭ Исходные данные для Робота записаны в файле 18-0.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вниз и вправо. Робот может брать монеты только с тех клеток, где количество монет чётно. Если количество монет нечётно, то Робот не берёт в этой клетке ни одной монеты, Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа (через пробел) - сначала максимальную сумму, затем минимальную. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз - соседнюю нижнюю. Файл Вредите паш ответ №18 Слож

Давайте разберем вашу задачу шаг за шагом!

Имеется робот, который перемещается по прямоугольной матрице (в данном случае - это таблица из файла 18-0.xls). Робот может двигаться только вниз и вправо, и его цель - собрать монеты из клеток, однако он может брать монеты только из тех клеток, где их количество четное.

Шаг 1: Понимание движения робота

Робот начинает в клетке (1,1) (левая верхняя) и должен добраться до клетки (n,m) (правая нижняя). По сути, он должен пройти по определенному маршруту, собирая монеты.

Шаг 2: Условия сбора монет

• Монеты можно собирать только из клеток с четным количеством.
• Если клетка содержит нечетное количество монет, робот не может их взять.

Шаг 3: Поиск максимальной и минимальной сумм

Чтобы определить максимальную и минимальную денежную сумму, которую может собрать робот, можно использовать подход динамического программирования.

1. Максимальная сумма монет:

   • Имеем массив (или матрицу) для хранения максимальной суммы монет на каждом шаге.
   • Заполняем его, начиная с верхней левой клетки и двигаясь вправо и вниз.
   • При переходе в каждую клетку проверяем, является ли количество монет четным. Если да, добавляем его к сумме, если нет - просто пропускаем.

2. Минимальная сумма монет:

   • Алгоритм аналогичен, но здесь мы будем искать минимальные значения, изменяя подход только на этапе сбора монет.

Пример кода (псевдокод):

# Предполагаем, что coins - это матрица, содержащая количество монет
max_sum = [[0]*m for _ in range(n)]
min_sum = [[float('inf')]*m for _ in range(n)]

# Инициализация стартовой точки
max_sum[0][0] = coins[0][0] if coins[0][0] % 2 == 0 else 0
min_sum[0][0] = coins[0][0] if coins[0][0] % 2 == 0 else float('inf')

for i in range(n):
    for j in range(m):
        if i > 0:
            if coins[i][j] % 2 == 0:
                max_sum[i][j] = max(max_sum[i][j], max_sum[i-1][j] + coins[i][j])
                min_sum[i][j] = min(min_sum[i][j], min_sum[i-1][j] + coins[i][j])
            else:
                max_sum[i][j] = max(max_sum[i][j], max_sum[i-1][j])
                min_sum[i][j] = min(min_sum[i][j], min_sum[i-1][j])
        
        if j > 0:
            if coins[i][j] % 2 == 0:
                max_sum[i][j] = max(max_sum[i][j], max_sum[i][j-1] + coins[i][j])
                min_sum[i][j] = min(min_sum[i][j], min_sum[i][j-1] + coins[i][j])
            else:
                max_sum[i][j] = max(max_sum[i][j], max_sum[i][j-1])
                min_sum[i][j] = min(min_sum[i][j], min_sum[i][j-1])

Заключение

После выполнения алгоритма в ячейке (n,m) у вас будут храниться максимальная и минимальная суммы монет, которые сможет собрать робот.

Введите ответ в формате: максимальная сумма минимальная сумма.

Если вам необходимо больше информации о том, как работать с файлами Excel для извлечения данных, или как реализовать алгоритм программирования, не стесняйтесь спрашивать! Успехов в учебе!