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

(А. Кабанов) Дана последовательность натуральных чисел. Рассматриваются всевозможные пары чисел, порядковые номера которых отличаются не более чем на 5. Определите количество таких пар, для которых сумма чисел меньше 100. Исходные данные записаны в виде столбца электронной таблицы в файле 18-k3.xls.

(А. Кабанов) Дана таблица натуральных чисел размера NxN (1 < N 20). Перемещаться между числами можно на одну клетку по горизонтали и вертикали (в любом направлении). Необходимо выбрать несколько подряд идущих чисел, таких, что каждое следующее число больше предыдущего. Какую максимальную сумму могут иметь выбранные числа?

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

(А. Кабанов) Дана таблица натуральных чисел размера NxN (1 < N 20). Перемещаться между числами можно на одну клетку по горизонтали и вертикали на одну клетку (в любом направлении). Необходимо найти самую длинную последовательность чисел, такую, что каждое следующее число больше предыдущего. В ответе запишите длину этой цепочки. 

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

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

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

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

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

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

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

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

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

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

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