18 - Динамическое программирование
в электронных таблицах

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

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

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

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

3) (№ 2369 В.Н.Шубинкин) Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. В любой клетке может быть стена (стены обозначены значениями больше 100, но меньше 500). При попытке выйти за границу квадрата или зайти на клетку со стеной Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

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

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

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

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

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

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

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

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

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

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

3,3 5,2 5,9 1,3 1,7 4,5

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

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

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

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

3,3 5,2 5,9 1,3 1,7 4,5

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

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

9) (№ 2514 А.Кабанов) Дана последовательность натуральных чисел. Из неё необходимо выбрать последовательность подряд идущих чисел так, чтобы каждое число было нечётным. Какую максимальную длину может иметь выбранная последовательность?

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

10) (№ 2515 А.Кабанов) Дана последовательность натуральных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое число было чётным. Какую максимальную сумму могут иметь выбранные числа?

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

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

12) (№ 2653 А.Кабанов) Дана последовательность натуральных чисел. Рассматриваются всевозможные пары чисел, порядковые номера которых отличаются не более чем на 5. Определите количество таких пар, для которых сумма чисел находится в диапазоне от 1000 до 1500, не включая 1000 и 1500.

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

13) (№ 2656 А.Кабанов) Дана последовательность натуральных чисел. Рассматриваются всевозможные пары чисел, порядковые номера которых отличаются не менее чем на 7. Определите количество таких пар, для которых сумма чисел находится в диапазоне от 1500 до 2000, включая 1500 и 2000.

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

14) (№ 2695 В.Н.Шубинкин) Исходные данные для Робота записаны в файле 18-0.xls в виде электронной таблицы прямоугольной формы. Число в каждой клетке обозначает количество монет, которые может взять Робот. Робот может двигаться только вниз и вправо. Робот может брать монеты только с тех клеток, где количество монет чётно. Если количество монет нечётно, то Робот не берёт в этой клетке ни одной монеты. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

15) (№ 2915 А.Богданов) Исходные данные для Робота записаны в файле 18-0.xls в виде электронной таблицы прямоугольной формы. Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки верхней строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в следующий ряд и может за одно перемещение попасть в одну из трех клеток следующей строки (на клетку прямо или боковые с ней). Ходы только в бок (без смены строки) и/или назад запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту.

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

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

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

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

18) (№ 3703 А.М.Кабанов) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы (внутренние, обозначенные жирными линиями, или границы квадрата) Робот разрушается. В каждой клетке квадрата указана плата за посещение в размере от 1 до 100. Посетив клетку, Робот платит за её посещение; это также относится к начальной и конечной точке маршрута Робота. Определите минимальную и максимальную денежную сумму, которую заплатит Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.

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

19) (№ 3706 А.М.Кабанов) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх – в соседнюю верхнюю. При попытке пересечь границы (внутренние, обозначенные жирными линиями, или границы квадрата) Робот разрушается. В каждой клетке квадрата указана плата за посещение в размере от 1 до 100. Посетив клетку, Робот платит за её посещение; это также относится к начальной и конечной точке маршрута Робота. Определите минимальную и максимальную денежную сумму, которую заплатит Робот, пройдя из правой нижней клетки в левую верхнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.

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