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

(А. Кабанов) Квадрат разлинован на N x N клеток (1 < N < 20). Исполнитель Буквоед может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы (внутренние, обозначенные жирными линиями, или границы квадрата) Буквоед разрушается. В каждой клетке квадрата указан её тип латинскими буквами A или B. Посетив клетку, Буквоед платит за её посещение; это также относится к начальной и конечной точке маршрута. За посещение клетки A взимается плата 10 монет, за посещение клетки B взимается плата 100 монет. Определите минимальную и максимальную денежную сумму, которую заплатит Буквоед, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала минимальную сумму, затем максимальную. Исходные данные записаны в электронной таблице 18-92.xls размером N x N, каждая ячейка которых соответствует клетке квадрата.

(Д. Муфаззалов, г. Уфа) Квадрат разлинован на N x N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх – в соседнюю верхнюю. При попытке пересечь границы квадрата Робот разрушается. В каждой клетке квадрата указано одно из двух чисел: 0 или 1. Если в клетке записано число 1, Робот может попасть в эту клетку, а если в клетке записано число 0, то робот не может попасть в такую клетку. Определите количество способов, которыми Робот может попасть из правой нижней клетки в левую верхнюю. В ответе укажите искомое число. Исходные данные записаны в электронной таблице 18-91.xls размером N x N, каждая ячейка которых соответствует клетке квадрата.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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