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

Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было меньше предыдущего. Какую максимальную сумму могут иметь выбранные числа? В ответе запишите целую часть полученной суммы. Исходные данные записаны в виде столбца электронной таблицы в файле 18-15.xls.

Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было больше предыдущего. Какую максимальную сумму могут иметь выбранные числа? В ответе запишите целую часть полученной максимальной суммы.

Например, для входных данных

3,3

5,2

5,9

1,3

1,7

4,5

максимально возможная сумма равна 14,4, в ответе надо записать число 14.

Исходные данные записаны в виде столбца электронной таблицы в файле 18-14.xls.

Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было меньше предыдущего. Какую максимальную сумму могут иметь выбранные числа? В ответе запишите целую часть полученной максимальной суммы.

Например, для входных данных

3,3

5,2

5,9

1,3

1,7

4,5

максимально возможная сумма равна 7,2, в ответе надо записать число 7.

Исходные данные записаны в виде столбца электронной таблицы в файле 18-14.xls.

(Е. Джобс) Квадрат разлинован на N×N клеток (3 < N < 17). В каждой клетке лежат конфеты, количество которых соответствует записанному числу. На поле работает исполнитель Дружище, который съедает все конфеты в клетке. Также, если исполнитель проходит между двумя четными или двумя нечетными значениями, то Добрый Волшебник дает ему еще 10 конфет, которые он, конечно же, сразу съедает. Так, например, если исполнитель приходит в клетку С3 из клетки В3, считается, что он прошел между клетками С2 и С4, если в С3 из С2 – между В3 и D3. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Дружище перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Дружище расстраивается, что ему не дают конфеты, и отказывается идти дальше.

Нам важно, чтобы Дружище съел как можно меньше конфет и при этом добрался из левой верхней клетки в правую нижнюю.

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

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

Для указанных входных данных ответом должно быть число – минимально возможное съедаемое количество конфет – 53.

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

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

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

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

Для указанных входных данных ответом должна быть пара чисел – минимальное и максимальное значения: 57 68

(Е. Джобс) Квадрат разлинован на N×N клеток (3 < N < 15). В каждой клетке записано целое число. На поле работает исполнитель Контур, которого можно разместить в любой клетке поля; далее он не перемещается. Контур суммирует числа во всех клетках вокруг клетки, в которой он находится. Для клеток, находящихся на краю квадрата, он находит сумму значений клеток, которые лежат внутри квадрата. Например, для ячейки А1 нужно найти сумму В1, А2, В2.

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

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

Для указанных входных данных ответом должна быть пара чисел – минимальное и максимальное значения: 9 70

(Е. Джобс) Квадрат разлинован на N×N клеток (3 < N < 15), где N – нечетное число. На поле работает 4 исполнителя Грузовичок, которые начинают движение из центральной клетки. Например, для N = 5 из клетки С3. Каждый исполнитель двигается в один из углов – левый верхний, правый верхний, левый нижний или правый нижний – и может двигаться соответственно только – налево и вверх, направо и вверх, вниз и влево, вниз и вправо.

Исполнители работают независимо друг от друга на своей копии поля. Каждая пройденная клетка содержит число – массу в килограммах забираемого груза. Цель исполнителя – забрать как можно большую массу груза (в килограммах). Необходимо найти наибольшую массу собранного груза для каждого Грузовичка. В ответе запишите четыре числа в порядке возрастания.

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

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

Для указанных входных данных ответом должна быть четверка чисел – результаты работы четырёх исполнителей в порядке возрастания:

30 35 47 55

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

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

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

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

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

(В.Н. Шубинкин, г. Казань) В любой клетке поля может быть стена (стены обозначены значениями больше 100, но меньше 500) или яма (ямы обозначены значениями меньше 0, но больше -400). Робот может двигаться только вниз или вправо. При попытке зайти на клетку со стеной Робот разрушается. При попытке зайти на клетку с ямой Робот застревает в ней и не может двигаться дальше.

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

(В.Н. Шубинкин, г. Казань) В любой клетке может быть яма (ямы обозначены значениями меньше 0, но больше -400). Робот может двигаться только вниз или вправо. При попытке зайти на такую клетку Робот застревает в яме и не может двигаться дальше. Исходные данные записаны в файле 18-12.xls в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, не застряв в яме. Известно, что такой путь существует. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(В.Н. Шубинкин, г. Казань) В любой клетке может быть стена (стены обозначены значениями больше 100, но меньше 500). Робот может двигаться только вниз или вправо. При попытке зайти на клетку со стеной Робот разрушается. Исходные данные записаны в файле 18-11.xls в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, не разрушившись. Известно, что такой путь существует. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные записаны в файле 18-10.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вверх или вправо. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

Исходные данные записаны в файле 18-9.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вверх или вправо. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

Исходные данные записаны в файле 18-8.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вверх или вправо. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

Исходные данные записаны в файле 18-7.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вверх или вправо. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

Исходные данные записаны в файле 18-6.xls в виде электронной таблицы прямоугольной формы. Робот может двигаться только вверх или вправо. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.