ЕГЭ-18. Обработка целочисленных данных в электронных таблицах (динамическое программирование)

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти поле с левой верхней клетки до правой нижней. Робот может двигаться по клеткам вправо, вниз или вправо и вниз (по диагонали). В каждой клетке поля лежит монета достоинством от 1 до 100. Робот не может ходить через стены или выходить за границы поля. Робот собирает все монеты по пройденному маршруту, включая верхнюю левую и нижнюю правую клетки. Определите минимально возможную денежную сумму, которую может собрать робот и общее количество клеток этого маршрута.

Исходные данные записаны в файле 18-164.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа: сначала минимальную сумму, затем общее количество клеток маршрута с минимальную суммой. Если маршрутов с минимальной суммой несколько, нужно выбрать наиболее короткий.

(Д. Статный) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Если значение в ячейке чётное, то роботу начисляется удвоенное количество монет, лежащих в ячейке, если нечётное – начисляется только половина значения ячейки, округлённое вниз при делении. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-163.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа — сначала количество ячеек с чётными значениями, находящихся на траектории движения Робота для максимальной суммы, а затем — то же самое для минимальной суммы. При подсчёте учитывать начальную и конечную ячейки.

(Г. Золотухин) Квадрат разлинован на N×N клеток (1 < N < 20). В каждой клетке находится некоторое количество монет, от 1 до 100. Исполнитель «Конь» движется с левой линии в правую линию. т. е. он может стартовать из любой клетки первого столбца и закончить маршрут в любой клетке последнего столбца таблицы. С каждой посещённой клетки исполнитель забирает с собой половину монет, если количество монет нечётное, то округление происходит в большую сторону.

Исполнитель может двигаться «ходом коня»: на две клетки вправо и на одну вверх или вниз, или на одну клетку вправо и на две клетки вверх или вниз. Определите максимальную и минимальную суммы, которые может собрать исполнитель.

Пример входных данных (для таблицы размером 5×5):

Для данного примера максимальная сумма получается при проходе коня по клеткам со значениями 54, 98, 46, 75 и 55; эта сумма равна 27+49+23+38+28=165. Минимальная сумма получается при проходе коня по клеткам со значениями 16, 46 и 15; эта сумма равна 8+23+8=39.

Ответ: 165 39.

Исходные данные записаны в файле 18-162.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальную сумму, затем минимальную.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 51 + 39 + 11 + 2 + 56 = 159. При этом робот проходит через 3 клетки с нечётными числами (51, 39, 11). В ответе в данном случае надо записать числа 159 и 3.

Исходные данные записаны в файле 18-156.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вверх, по диагонали влево-вверх или по диагонали вправо-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 68 + 46 + 11 + 26 = 151. При этом робот проходит через 3 клетки с чётными числами (68, 46, 26). В ответе в данном случае надо записать числа 151 и 3.

Исходные данные записаны в файле 18-156.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с чётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вниз, по диагонали влево-вниз или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 56 + 2 + 11 + 39 + 51 = 159. При этом робот проходит через 2 клетки с чётными числами (56, 2). В ответе в данном случае надо записать числа 159 и 2.

Исходные данные записаны в файле 18-154.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с чётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали вправо-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 26 + 11 + 46 + 68 = 151. При этом робот проходит через 1 клетку с нечётным числом (11). В ответе в данном случае надо записать числа 151 и 1.

Исходные данные записаны в файле 18-154.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали вправо-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 51 + 89 + 24 + 39 + 12 + 46 + 68 + 38 + 41 + 56 = 464. При этом робот проходит через 4 клетки с нечётными числами (51, 89, 39, 41). В ответе в данном случае надо записать числа 464 и 4.

Исходные данные записаны в файле 18-156.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вверх, по диагонали влево-вверх или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 68 + 38 + 41 + 56 + 15 + 39 + 51 + 89 + 18 + 26 = 441. При этом робот проходит через 5 клеток с чётными числами (68, 38, 56, 18, 26). В ответе в данном случае надо записать числа 441 и 5.

Исходные данные записаны в файле 18-156.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с чётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вниз, по диагонали влево-вниз или по диагонали вправо-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 56 + 2 + 44 + 15 + 38 + 46 + 39 + 89 + 24 + 51 = 404. При этом робот проходит через 6 клеток с чётными числами (56, 2, 44, 38, 46, 24). В ответе в данном случае надо записать числа 404 и 6.

Исходные данные записаны в файле 18-154.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с чётными значениями.

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

количество пройденных клеток с нечётными значениями.

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 26 + 44 + 18 + 11 + 89 + 39 + 46 + 38 + 12 + 68 = 391. При этом робот проходит через 3 клетки с нечётными числами (11, 89, 39). В ответе в данном случае надо записать числа 391 и 3.

Исходные данные записаны в файле 18-154.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с запада (левый столбец) на восток (правый столбец). Он может начать переход с любой клетки левого столбца и закончить на любой клетке правого столбца. С каждым шагом Робот переходит в следующий столбец и может за одно перемещение попасть в одну из трех клеток следующего столбца (на клетку вправо или боковые с ней, вправо-вниз или вправо-вверх). Ходы только вверх или вниз (без смены столбца) и назад (в предыдущий столбец) запрещены.

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

Исходные данные записаны в файле 18-153.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала максимальный сбор монет, затем – количество пройденных клеток с нечётными значениями

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается на две клетки вправо, по команде вверх – на две клетки вверх. При попытке выхода за границу квадрата Робот телепортируется на противоположную сторону. Например, если из крайней правой клетки выполнить команду вправо, робот переместится во второй столбец этой же строки. Перед каждым запуском Робота в каждой клетке квадрата записано число от 10 до 99. Посетив клетку, Робот прибавляет к своему счету записанное в ней значение. После посещения клетки число в ней обнуляется. Определите максимальное и минимальное значение счета, который может набрать Робот, пройдя из левой нижней клетки в правую верхнюю.

Пример входных данных (для поля 3х3):

Для указанных входных данных ответом должна быть пара чисел 47 и 15.

Исходные данные записаны в файле 18-152.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальное значение, затем минимальное.

(И. Женецкий) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вверх или вправо. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает все монеты с собой в том случае, если в клетке нечётное количество монет, иначе - половину. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в правую верхнюю.

Исходные данные записаны в файле 18-151.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальное значение, затем минимальное.

*(Д. Статный) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вверх или вправо. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. На поле имеются зелёные клетки, в которые Робот может зайти, сохранив все накопленные ранее монеты, если перед этим количество собранных монет было чётным, в противном случае, он теряет все собранные монеты и начинает сбор с 0 (монеты, находящиеся в клетке, не идут в счет). Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в верхнюю правую.

Исходные данные записаны в файле 18-150.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала минимальное значение, затем максимальное.

*(Д. Статный) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Попрыгунчик может прыгать по клеткам, выполняя за одно перемещение одну из четырёх команд: вниз, вверх, вправо и влево. По команде вправо или влево Попрыгунчик перемещается в соседнюю правую или левую клетку соответственно, по команде вниз и вверх – в соседнюю нижнюю или верхнюю клетку соответственно. Команды вправо и влево доступны, когда нет возможности применить команды вверх и вниз. Проход по одним и тем же полям запрещен. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Попрыгунчик перепрыгнуть не может. Перед каждым запуском Попрыгунчика в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Попрыгунчик забирает монеты из полей; это также относится к начальной и конечной клеткам маршрута. Найдите максимальную и минимальную денежные суммы, которые может иметь Попрыгунчик, дойдя до середины поля (эта клетка выделена фоном) из верхней левой клетки.

Исходные данные записаны в файле 18-149.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальное значение, затем минимальное.

(Информатик-БУ) Квадрат разлинован на N×N клеток (1 < N < 12). Исполнитель Змейка может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Змейка перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенками, сквозь стену Змейка пройти не может. В некоторых клетках квадрата расположены двоичные цифры (0 или 1). Посетив клетку с цифрой, Змейка подставляет её к своему хвосту. Например, посетив клетку с единицей, Змейка вида «1011» превратится в «11011», а посетив клетку с нулём – в «01011». Определите максимальное и минимальное значение Змейки после того, как она пройдет из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-148.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальное значение, затем минимальное. Ответы запишите в десятичной системе счисления.

(Информатик-БУ) Квадрат разлинован на N×N клеток (1 < N < 12). Исполнитель Змейка может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Змейка перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенками, сквозь стену Змейка пройти не может. В некоторых клетках квадрата расположены двоичные цифры (0 или 1). Посетив клетку с цифрой, Змейка подставляет её к своей голове. Например, посетив клетку с единицей, Змейка вида «1011» превратится в «10111», а посетив клетку с нулём – в «10110». Определите максимальное и минимальное значение Змейки после того, как она пройдет из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-147.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальное значение, затем минимальное. Ответы запишите в десятичной системе счисления.

(М. Ишимов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой в том случае, если робот не находится на начальной или конечной клетке, а также если стоимость монеты нечётная.

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

Исходные данные записаны в файле 18-146.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вверх или влево. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из правой нижней клетки в верхнюю левую.

Исходные данные записаны в файле 18-145.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.