Динамическое программирование python егэ - Помощь в подготовке к экзаменам и поступлению

23-е задание: «Динамическое программирование и анализ работы алгоритма»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 8 минут.

Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма

До ЕГЭ 2021 года — это было задание № 22 ЕГЭ

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

23_4: Разбор досрочного ЕГЭ по информатике 2019:

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

Прибавить 1

Умножить на 2

Сколько существует программ, для которых при исходном числе 3 результатом является число 37 и при этом траектория вычислений содержит число 18?

Ответ: 28

📹 Видео

📹 Видеорешение на RuTube здесь

23_2:

У исполнителя Увеличитель две команды, которым присвоены номера:

прибавь 1

умножь на 4

Первая из них увеличивает число на экране на 1, вторая умножает его на 4.

Программа для Увеличителя – это последовательность команд.

Сколько есть программ, которые число 3 преобразуют в число 44?

Ответ: 10

✍ Показать решение:

Использование графов

Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:

12 
к нему применима только команда - прибавь 1 
12 * 4 = 48 - это больше, чем 44

Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):

Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.

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

для 11 взят результат, полученный для 12 (1);
для 10 взят результат, полученный для числа 11 (2);
для 9 взят результат, полученный для 10 (3);
и т.д.

Для последнего числа 3 получено 10 команд.

📹 Видео (теоретическое решение)

📹 Видеорешение на RuTube здесь (теоретический способ)

23_3. Демоверсия ЕГЭ 2018 информатика:

Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Ответ: 60

✍ Показать решение:

Изобразим траекторию в виде луча, на котором отложим отрезки:

Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:

1 * 2 * 3
или
(2 -> 8) * (8 -> 10) * (10 -> 12)

Найдем отдельно количество программ каждого из отрезков:
2 -> 8 = 15
На интервале от 2 до 8 возьмем наименьшее число, для которого исполнима только одна из команд:

7
7 + 1 = 8
7 + 2 = 9 - нельзя, вне интервала

Рассмотрим все числа интервала, двигаясь от большего к меньшему:

8 -> 10 = 2
очевидно, что это две программы:

10 -> 12 = 2

Выполним произведение полученных результатов:

15 * 2 * 2 = 60

📹 Видео (теоретическое решение)

📹 Видеорешение на RuTube здесь

Источник

Динамическое программирование

Динамическое программирование (или коротко динамика) — это подход к решению достаточно широкого класса задач, в котором решение исходной задачи строится на основе решения подзадач.
Слово «программирование» в названии «динамическое программирование» имело не тот смысл, что сейчас: когда Ричард Беллман придумал этот термин,
составление программ не было массовой профессией и названия для этой профессии не было.
В те времена программирование означало «планирование» и под «динамическим программированием» понималось оптимальное планирование многоступенчатых процессов.

Совсем в общем виде подход состоит в том, чтобы вместо одной исходной задачи, придумать множество подзадач так, чтобы исходная была среди них, но при этом каждая из подзадач «легко» выводится из «предыдущих».
Если говорить формально, то сначала определяется множество подзадач. Их мы располагаем в вершинах графа. Дальше мы проводим ориентированные рёбра из одной подзадачи в другую, если решение первой помогает во второй. Если в результате получился «не слишком большой» ациклический граф (если есть циклы, то всё пропало!), то задача решается динамическим программированием. Известно, что вершины ациклического графа можно так обойти, чтобы на каждом шаге не встречать не решённых зависимостей.

Начнём с простого примера: числа Фибоначчи. Они определяются так: $F_1 = 1$, $F_2 = 1$, $F_{i+1} = F_{i} + F_{i-1}$.
Если наша исходная задача — это вычислить $F_n$, то подзадачи — это вычисление $F_1, F_2, ldots, F_{n-1}, F_n$.
Каждая подзадача $F_i$ легко решается на основе ответов в подзадачах $F_{i-1}$ и $F_{i-2}$.
Ациклический граф подзадач выглядит следующим образом:

Стандартные види динамики

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

Вычисляем простую последовательность. Исходную задачу можно включить в вычисление элементов последовательности $x_1, x_2, ldots, x_n$, подзадачи — вычисление значений $x_i$ для $i le n$, причём $x_i$ вычисляется на основе фиксированного количества предыдущих членов (как в примере с числами Фибоначчи). Сложность решения — $O(n)$. Пример задачи — числа Фибоначчи и последовательности, заданные рекуррентными соотношениями.
Вычисляем сложную последовательность. То же самое, что в предыдущем пункте, но $x_i$ вычисляется на основе всех предыдущих членов. Сложность решения — $O(n^2)$. Достаточно часто существует оптимизация решения до $O(n log n)$;
Вычисляем две последовательности. Исходную задачу можно включить в вычисление элементов последовательностей $x_1, x_2, ldots, x_m$ и $y_1, y_2, ldots, y_n$. Подзадачи — вычисление конкретных $x_i$ и $y_j$. Каждый из $x_i$ и $y_j$ легко вычисляются на основе фиксированного набора предыдущих членов. Сложность решения — $O(mn)$;
Вычисляем двумерный массив. Исходную задачу можно включить в вычисление элементов прямоугольного массива $x_{11}, x_{12}, ldots, x_{1m}, x_{21}, ldots, x_{nm}$, подзадачи — вычисление конкретных $x_{ij}$, причём $x_{ij}$ вычисляется на основе фиксированного количества предыдущих членов. Сложность решения — $O(mn)$. Пример задачи — вычисление редакционного расстояния между двумя строками;
Обрабатываем последовательность. Задача ставится для данной последовательности $x_1, x_2, ldots, x_n$, подзадачи — та же задача для префиксов $x_1, x_2, ldots, x_i$, $i < n$ этой последовательности. Пример задачи — нахождение наибольшей возрастающей подпоследовательности, нахождение самой длинной подпоследовательности-палиндрома. Число подзадач $O(n)$. Типичная сложность — $O(n^2)$, которая часто оптимизируется до $O(n log n)$;
Динамика на подотрезках. Сложная обработка последовательности. Требуется обработка последовательности $x_1, x_2, ldots, x_n$, но подзадачи — это решения для всех подотрезков $x_i, ldots, x_j$ для $i, j < n$. Число подзадач — $O(n^2)$.
Вычисляем последовательности со сложными зависимостями. Сводим к вычислению двух последовательностей или прямоугольного массива, но каждый элемент зависит от существенной части «предыдущих». Сложность до $O(n^2m^2)$. Довольно часто существуют оптимизация до $O(n^3)$ или даже до $O(n^2)$.
Обрабатываем данный прямоугольный массив. Подзадачи — решения для «подпрямоугольников». Хорошо, если вершина подпрямоугольника лежит в левом верхнем углу.
Обрабатываем две данных последовательности чисел $x_1, x_2, ldots, x_m$ и $y_1, y_2, ldots, y_n$. Подзадачи — тот же вопрос для префиксов $x_1, ldots, x_i$ и $y_1, ldots, y_j$. Число подзадач — $O(nm)$, сложность — от $O(mn)$ до $O(n^2m^2)$. Пример задачи — нахождение наибольшей общей подпоследовательности двух последовательностей;
Динамика по подмножествам. В динамике по подмножествам подзадачи — это тот же вопрос для подмножества. Обычно в параметр входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Число подзадач — $O(2^n)$. Примеры задач — задача коммивояжера.
Динамика по поддеревьям. Подзадачи соответствуют поддеревьям в исходном дереве.
Динамика по профилю (по изломанному профилю). Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Подзадачи — тот же вопрос для части поля. В простом случае граница этой части прямая, в сложном — у неё есть излом (получается изломанный профиль).

Стандартные шаги решения

Чтобы успешно решить задачу динамикой нужно:

Разбиение на подзадачи и понимание того, как выводить одну из другой;
Состояние динамики — параметр(ы), однозначно задающие подзадачу;
Начальные состояния (те части, где ответ очевиден);
Зависимости и переходы между состояниями. Здесь нужна формула, по которой мы получаем решение подзадачи на основе предыдущих;
Порядок пересчёта. Про это чуть дальше;
Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.

Разберёмся снова на примере задачи о числах Фибоначчи.

Состояние динамики: номер числа Фибоначчи;
Начальные состояния: $F_1 = F_2 = 1$;
Зависимости и переходы между состояниями. $F_{i}=F_{i-1}+F_{i-2}$;
Порядок пересчёта. Про это чуть дальше;
Положение ответа на задачу: ответ — это просто $F_{n}$.

Снизу вверх или сверху вниз

Теперь о порядке пересчёта. Существуют два подхода к решению: снизу вверх и сверху вниз.

«Ленивая» рекурсивная динамика сверху вниз

Подход сверху вниз — это использование рекурсивной функции, в которую встроена мемоизация — сохранение единожды вычисленного результата для того, чтобы не повторять вычислений предыдущих шагов. Примеры реализации:

n = 100
known_fibs = [None] * (n+2)        # Таблица для мемоизации. None — значит «ещё не вычислили»
known_fibs[1] = known_fibs[2] = 1  # Начальные известные состояния
def calc_fib(i):
    if known_fibs[i] is None:      # Значение ещё не посчитано
        known_fibs[i] = calc_fib(i - 1) + calc_fib(i - 2)  # Применяем формулу
    return known_fibs[i]  # Готово
print(calc_fib(n))

Иногда в питоне можно попробовать «схалтурить» и применить встроенное кеширование:

from functools import lru_cache
@lru_cache(maxsize=n)       # Эта штука автоматом запоминает maxsize последних значений функции
def cache_fib(i):           # Благодаря этому код становится чрезвычайно простым
    if i == 1 or i == 2:
        return 1
    return cache_fib(i - 1) + cache_fib(i - 1)
print(cache_fib(100))

Во многих случаях встроенных кеш работает примерно столь же бысто, что и «ручной».
Поэтому может быть полезно начать именно с такого решения.

Динамика снизу вверх

При подходе снизу вверх последовательно решаются все промежуточные подзадачи и их решения заносятся в «таблицу».
Плюс этого подхода — нет ограничения на глубину рекурсии и дополнительных затрат на вызовы функций.
Минус — неизбежно будут вычислены все промежуточные значения, даже если они по большому счёту не были нужны.
При пересчёте есть два варианта заполнения: прямой порядок и обратный.
Прямой порядок — решение подзадачи вычисляется на основе уже известных и сразу заносится в «таблицу».

n = 100
def forward_fib(n):
    known_fibs = [None] * (n+2)        # Таблица ответов на подзадачи. None — значит «ещё не вычислили»
    known_fibs[1] = known_fibs[2] = 1  # Начальные известные состояния
    for i in range(3, n + 1):
        known_fibs[i] = known_fibs[i - 1] + known_fibs[i - 2]
    return known_fibs[n]
print(forward_fib(n))

Обратный порядок — к тому моменту, как мы «пришли» к подзадаче, ответ на неё уже вычислен.
И мы подправляем ответ на подзадачи, которые от текущей зависят.

n = 100
def backward_fib(n):
    known_fibs = [0] * (n+2)           # Таблица ответов на подзадачи. Здесь нули важны
    known_fibs[0] = 0                  # Начальные известные состояния
    known_fibs[1] = 1                  # Начальные известные состояния
    for i in range(1, n):
        known_fibs[i + 1] += known_fibs[i]  # Подзадача i решена, разносим её «вклад» в другие подзадачи
        known_fibs[i + 2] += known_fibs[i]
    return known_fibs[n]
print(backward_fib(n))

Каждый из этих способов подсчёта имеет свою область применения, хотя часто пересекающуюся с другими.
Перечисленные выше экземпляры кода вычисляют 2000-е число Фибоначчи примерно за следующее время:

кеш — 0.0025c;
мемо — 0.0023c;
forw — 0.00076c;
back — 0.0013c.

Вводные задачи

A: Мячик на лесенке

На вершине лесенки, содержащей $N$ ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через $2$. (То есть, если мячик лежит на $8$-ой ступеньке, то он может переместиться на $5$-ую, $6$-ую или $7$-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Вводится одно число $0 < N < 31$.

Выведите одно число — количество маршрутов.

B: Последовательность из 0 и 1

Требуется подсчитать количество последовательностей длины $N$, состоящих из $0$ и $1$, в которых никакие две единицы не стоят рядом.

На вход программы поступает целое число $N$ $(1 leqslant N leqslant 10^5)$.

Выведите количество искомых последовательностей по модулю $10^9+7$.

C: Без трёх единиц

Определите количество последовательностей из нулей и единиц длины $N$ (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.

Вводится натуральное число $N$, не превосходящее $40$.

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит $2^{31}-1$.

D: Платная лестница

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.

В первой строке входного файла вводится одно натуральное число $N leqslant 100$ — количество ступенек.
В следующей строке вводятся $N$ натуральных чисел, не превосходящих $100$ — стоимость каждой ступеньки (снизу вверх).

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Одномерное динамическое программирование

E: Радиоактивные материалы

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной.

Для заданного количества контейнеров $N$ определить число безопасных стопок.

На вход программе подаётся одно число $1 leqslant N leqslant 10^5$.

Программа должна вывести одно число — количество безопасных вариантов формирования стопки, взятое по модулю $10^9+7$.

F: Поход вдоль реки

Дети пошли в поход вдоль реки. Поход начинается на левом берегу, заканчивается на правом. Дана последовательность букв ‘L’, ‘R’, ‘B’, означающая с какой стороны в реку впадает приток: ‘L’ — слева (left), ‘R’ — справа (right), ‘B’ — с обеих сторон (both). Определить минимальное количество переправ, которое придётся сделать школьникам.

На вход программа получает строку, содержащую только символы R, L, B в произвольном порядке. Длина строки не превосходит $10^5$ символов.

Выведите одно целое число — минимальное количество переправ.

G: Гвоздики

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

В первой строке входных данных записано число $N$ — количество гвоздиков $(2 leqslant N leqslant 100)$. В следующей строке заданы $N$ неотрицательных целых чисел, не превосходящие $10000$ — координаты всех гвоздиков в порядке возрастания.

Выведите единственное число — минимальную суммарную длину всех ниточек.

H: Покупка билетов

За билетами на премьеру нового мюзикла выстроилась очередь из $N$ человек, каждый из которых хочет купить $1$ билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

Однако для борьбы со спекулянтами кассир продавала не более $3$-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь $2$ или $3$ подряд стоящих человека.

Известно, что на продажу $i$-му человеку из очереди одного билета кассир тратит $A_i$ секунд, на продажу двух билетов — $B_i$ секунд, трех билетов — $C_i$ секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

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

На вход программы поступает сначала число $N$ — количество покупателей в очереди $(1 leqslant N leqslant 5000)$. Далее идет $N$ троек натуральных чисел $A_i, B_i, C_i$. Каждое из этих чисел не превышает $3600$. Люди в очереди нумеруются, начиная от кассы.

Требуется вывести одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.

5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1

I: Калькулятор с восстановлением ответа

Имеется калькулятор, который выполняет три операции:

1. прибавить к числу $X$ единицу;
2. умножить число $X$ на $2$;
3. умножить число $X$ на $3$;

Определите кратчайшую последовательность операций, необходимую для получения из числа $1$ заданное число $N$ $(1 leqslant N leqslant 10^6)$.

Выведите строку, состоящую из цифр 1, 2 или 3, обозначающих одну из трех указанных операций, которая получает из числа $1$ число $N$ за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.

562340

3333312222122213312

J: Наибольшая возрастающая подпоследовательность за $O(n^2)$

Дана последовательность чисел длины $n$. Определить длину наибольшей возрастающей подпоследовательности этой последовательности.

В этой задаче предполагается решение со сложностью $O(n^2)$.

Рассмотрим величину $d_i$ — длину максимальной подпоследовательности, заканчивающейся элементом $x_i$. Тогда:
$$d[0] = 1; d_i = 1 + max{d_j: 0 leqslant j leqslant i-1, x[j] < x[i]}$$
Здесь используется следующий факт — если отбросить $x_i$ из подпоследовательности длины $d[i]$, то подпоследовательность длины $d[i]-1$, заканчивающаяся каким-то $x_j$ также будет оптимальной, т.е. иметь максимальную длину из всех возможных, заканчивающихся элементом $x_j$.

Результат: $max{d[j]: 0 leqslant j leqslant n-1}$

В первой строке входных данных задано число $N$ — длина последовательности $(1 leqslant N leqslant 1000)$. Во второй строке задается сама последовательность — целые числа, не превосходящие $10000$ по модулю.

Требуется вывести длину наибольшей строго возрастающей подпоследовательности.

K: Наибольшая возрастающая подпоследовательность с восстановлением ответа за $O(n^2)$

Дана последовательность чисел длины $n$. Определить наибольшую возрастающую подпоследовательность этой последовательности.

В этой задаче предполагается использовать решение предыдущей задачи со сложностью $O(n^2)$, но вместо длины вывести пример такой подпоследовательности. Если есть несколько подпоследовательностей максимальной длины — вывести любую.

L: Наибольшая возрастающая подпоследовательность с восстановлением ответа за $O(ncdot log{n})$

Оказывается, предыдущую задачу можно решить гораздо быстрее (за $ncdot log{n}$), изменив схему динамического программирования.

Рассмотрим $d_i$ — минимальное число, на которое заканчивается возрастающая подпоследовательность длины $i$ (для программирования надо запоминать не значение, а его индекс, но думать проще про значение).

Поскольку $d_{i-1 }leqslant d_i$ для всех $i=1ldots n$ и каждый элемент x[i] обновляет максимум одну ячейку массива d, то для вычисления d можно использовать бинарный поиск.

Числовая последовательность задана рекуррентной формулой: $a_{i+1}=(k a_i+b)% m$. Найдите её наибольшую возрастающую подпоследовательность.

Программа получает на вход пять целых чисел: длину последовательности $N$ $(1 leqslant N leqslant 10^5)$, начальный элемент последовательности $a_1$, параметры $k,b,m$ для вычисления последующих членов последовательности $(1 leqslant m leqslant 10^4,0 leqslant k < m, 0 leqslant b < m,0 leqslant a_1 < m)$.

Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности, разделяя числа пробелами. Если таких последовательностей несколько, необходимо вывести одну (любую) из них.

Двумерное динамическое программирование

M: Количество маршрутов

В прямоугольной таблице $Ntimes M$ игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз. При этом некоторые клетки таблицы посещать запрещено. Определите количество маршрутов, проходящих по разрешённым клеткам, которые ведут в правую нижнюю клетку. Гарантируется, что левая верхняя и правая нижняя клетки доступны.

Вводятся два числа $N$ и $M$ — размеры таблицы $(1 leqslant N leqslant 1000, 1 leqslant M leqslant 1000)$. Затем в $N$ строках вводится по $M$ чисел: $1$ означает, что в клетку можно попасть, $0$ – что клетка недоступна.

Выведите искомое количество способов или слово Impossible, если это сделать невозможно. Гарантируется, что ответ не превосходит $2cdot 10^9$.

3 5
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1

N: Самый дешёвый путь

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

Входные данные содержат два числа $N$ и $M$ — размеры таблицы $(1 leqslant N leqslant 20, 1 leqslant M leqslant 20)$, а в следующих $N$ строках по $M$ чисел в каждой — размеры штрафов за прохождение через соответствующие клетки (числа от $0$ до $100$).

5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1

O: Вывести маршрут максимальной стоимости

В левом верхнем углу прямоугольной таблицы размером $Ntimes M$ находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

В первой строке входных данных записаны два натуральных числа $N$ и $M$, не превосходящих $100$ — размеры таблицы. Далее идет $N$ строк, каждая из которых содержит $M$ чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от $0$ до $100$.

Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать $N-1$ букву D, означающую передвижение вниз и $M-1$ букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9

74
D D R R R R D D

P: Наибольшая общая подпоследовательность

Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности.

В первой строке входных данных содержится число $N$ — длина первой последовательности $(1 leqslant N leqslant 1000)$. Во второй строке заданы члены первой последовательности (через пробел) — целые числа, не превосходящие $10000$ по модулю.

В третьей строке записано число $M$ — длина второй последовательности $(1 leqslant M leqslant 1000)$. В четвертой строке задаются члены второй последовательности (через пробел) — целые числа, не превосходящие $10000$ по модулю.

Требуется вывести одно число — длину наибольшей общей подпоследовательности двух данных последовательностей или $0$, если такой подпоследовательности нет.

Q: Наибольшая общая подпоследовательность с восстановлением ответа

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

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

Если длина общей подпоследовательности равна нулю, во второй строке ничего выводить не надо.

R: Расстояние по Левенштейну

Дана текстовая строка. С ней можно выполнять следующие операции:

Заменить один символ строки на другой символ.
Удалить один произвольный символ.
Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки СОК можно получить строку СУК, при помощи второй операции — строку ОК, при помощи третьей операции — строку СТОК.

Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.

Определите расстояние Левенштейна для двух данных строк.

Программа получает на вход две строки, длина каждой из которых не превосходит $1000$ символов, строки состоят только из заглавных латинских букв.

Требуется вывести одно число — расстояние Левенштейна для данных строк.

Динамическое программирование на подотрезках

S: Распил брусьев

Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет $k$ рублей за распил одного бруска длиной $k$ метров на две части.

Понятно, что различные способы распила приводят к различной суммарной стоимости заказа.

Например, рассмотрим брус длиной $10$ метров, который нужно распилить на расстоянии $2$, $4$ и $7$м, считая от одного конца. Это можно сделать несколькими способами.

Можно распилить сначала на отметке $2$, потом $4$ и, наконец, $7$ м. Это приведет к стоимости $10+8+6=24$, потому что сначала длина бруса, который пилили, была $10$ м, затем она стала $8$м, и, наконец, $6$м.

А можно распилить иначе: сначала на отметке $4$, затем $2$, затем $7$м. Это приведет к стоимости $10+4+6=20$, что выгоднее.

Определите минимальную стоимость распила бруса на заданные части.

Первая строка входных данных содержит целое число $L$ $(2 leqslant L leqslant 10^6)$ — длину бруса и целое число $N$ $(1 leqslant N leqslant 100)$ — количество распилов. Во второй строке записано $N$ целых чисел $C_i$ $(0 < C_i < L)$ в строго возрастающем порядке — места, в которых нужно сделать распилы.

Выведите одно натуральное число — минимальную стоимость распила.

T: Предприниматели и золото

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

На вход подаётся число $1 leqslant N leqslant 50$ — количество
кошельков, а в следующей строке $N$ целых положительных чисел, не превосходящих $100000$, описывающих количество золота в кошельках. Требуется вычислить и вывести одно число — насколько сумма А окажется больше суммы Б (если у А окажется меньше денег, напечатайте соответствующее отрицательное число).

U: Одномерная змейка

Цель игрока в компьютерной игре Snake1D — привести ползающую по прямой змею из координаты $x_1$ в координату $x_2$. Первоначальная скорость змеи равна $1$, а в некоторых местах на прямой расположены бонусы, поедание которых ускоряет змею в два раза.

На вход подаются два целых числа $0 leqslant x_1,x_2 leqslant 1000000$, целое число $0 leqslant N leqslant 50$ и $N$ целых чисел в диапазоне $[0..1000000]$ координаты бонусов.
Бонусы можно считать точечными и поедаемыми мгновенно, никакие два бонуса не находятся в одной точке, в точках $x_1$ и $x_2$ бонусов нет.

Напечатайте минимальное время, за которое змея сможет добраться из точки $x_1$ в точку $x_2$. Ответ должен отличаться от правильного не
более чем на $10^{-7}$.

Комментарии к тесту:

Оптимальной стратегией в этом случае будет вернуться из точки $10$ в точку $8$, увеличить там скорость до $2$, направиться в $18$, где увеличить скорость до $4$ и дойти наконец до точки $20$. Всего будет затрачено время $$|10-8|times1+|18-8|times0.5+|20-18|times0.25=7.5$$ Это быстрее, чем идти из точки $10$ сразу в сторону точки $20$.

Источник

Здравствуйте! Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2023.

Двадцать третье задание является последним заданием из первой части ЕГЭ по информатике 2023.

Давайте познакомимся с примерными задачами 23 задания из ЕГЭ по информатике 2023.

Задача (классическая)

У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавить 3,
2. умножить на 2.

Первая из них увеличивает число на экране на 3, вторая — удваивает его.

Программа для Удвоителя — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 25 ?

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+3, y) + F(x*2, y)

print(F(1, 25))

Число x, это то число, с которым мы работаем. Число y — это куда нужно прийти.

Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.

Ответ получается равен 9.

2 Способ (графический, для понимания)

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

Видим, что количество программ получается 9!

3 Способ (С помощью таблицы)

Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i — чётное).

Числа	1	2	3	4	5	6	7	8	9	10
+3	—	—	—	1	2	3	4	5	6	7
*2	—	1	—	2	—	3	—	4	—	5
Кол. Прог.	1	1	0	2	1	0	2	3	0	3

Числа	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
+3	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
*2	—	6	—	7	—	8	—	9	—	10	—	11	—	12	—
Кол. Прог.	3	0	3	5	0	6	5	0	6	8	0	9	8	0	9

В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).

Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)

В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)

В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).

Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!

Получаем ответ 9!

Ответ: 9

Задача (с избегаемым узлом)

Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y or x==24: return 0

    if x < y: return F(x+1, y) + F(x*2+1, y)

print(F(1, 25))

Здесь на нельзя получать число 24, поэтому, если x будет равен 24, то мы возвращаем ноль.

Ответ получается равен 10.

2 способ (Решение с помощью таблицы).

Мы не может получать число 24! Значит, единственным способом добраться до числа 25 будет вторая команда.

Получается, что сначала нужно получить число 12, тогда 2 * 12 + 1 = 25 (2x+1). Это единственный путь!

Каждое число можем получить только 2 способами (Либо с помощью первой команды, либо с помощью второй команды). Поэтому количество программ для некоторого числа i будет равно сумме количеств команд для числа i-1 и для числа (i — 1) / 2 (Если число нечётное.) Если число i — чётное, то до числа i можно добраться единственным способом (с помощью первой команды).

Если записать с помощью массива:

A[i]=A[i-1] — если i — четное.
A[i]=A[i-1] + A[(i-1)/2] — если i нечетное;

Числа	1	2	3	4	5	6	7	8	9	10	11	12
2x+1	—	—	1	—	2	—	3	—	4	—	5	—
+1	—	1	2	3	4	5	6	7	8	9	10	11
Кол. Прог.	1	1	2	2	3	3	5	5	7	7	10	10

Ответ: 10

Задача (ЕГЭ по информатике, Москва, 2019)

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает его на 2.

Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит число 9 и число 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(2, 9)*F(9, 11)*F(11, 12))

У нас числа 9 и 1 обязательные, поэтому разбиваем функцию следующим образом F(2, 9)*F(9, 11)*F(11, 12), через умножение. Это и будет ответ. Получается 50.

2 способ (с помощью таблицы).

От числа 11 до числа 12 можно добраться единственным путём (11 + 1 = 12).

От числа 9 до числа 11 можно добраться двумя способами (9 + 1 + 1 = 11, 9 + 2 = 11).

Найдём сколькими способами можно попасть от числа 2 до числа 9.

Числа	2	3	4	5	6	7	8	9
+1	—	2	3	4	5	6	7	8
*3	—	—	—	—	2	—	—	3
+2	—	—	2	3	4	5	6	7
Кол-во программ	1	1	2	3	6	9	15	25

Учитывая, что от 9 до 11 двумя способами можно добраться, то 25 * 2 = 50 — это и будет ответ.

Ответ: 50

Задача ( ЕГЭ по информатике, Москва, 2020)

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9?

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(3, 9)*F(9, 14))

Ответ получается 112.

2 способ (с помощью таблицы).

Последней командой для получении любого числа из траектории программы может быть одна из трёх выше указанных команд!

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

Получается, что мы будем использовать основной принцип 23 задания из ЕГЭ по информатике: результат для некоторого числа опирается на результаты предыдущих чисел. Т.к. траектория вычислений программ обязательно должна проходить через число 9, то при вычислении результата для чисел больших 9, мы не можем опираться на результаты для чисел меньших 9 (Иначе мы пропустим число 9).

Числа	3	4	5	6	7	8	9	10	11	12	13	14
+1	—	3	4	5	6	7	8	9	10	11	12	13
*3	—	—	—	—	—	—	3	—	—	—	—	—
+2	—	—	3	4	5	6	7	—	9	10	11	12
Кол-во программ	1	1	2	3	5	8	14	14	28	42	70	112

Ответ: 112

Посмотрим следующую задачу из 23 задания ЕГЭ по информатике 2023

Задача (с обязательным узлом, закрепление)

Исполнитель Май17 преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x+3, y)

print(F(1, 9)*F(9, 17))

Ответ получается 169.

2 способ (с помощью таблицы).

Любое число может получится в результате двух команд! Тогда количество программ для числа i будет складываться из количеств команд для числа i — 1 и для числа i — 3.

Если написать на языке массива

A[i] := A[i-1] + A[i-3], при i > 3.

Числа	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
+1	—	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
+3	—	—	—	1	2	3	4	5	6	—	—	9	10	11	12	13	14
Кол-во программ	1	1	1	2	3	4	6	9	13	13	13	26	39	52	78	117	169

При составлении значения для числа 10, мы не имеем право «заглядывать» за число 9, иначе число 9 будет пропущено! Поэтому для следующих трёх чисел (9, 9 + 1, 9 + 1 + 1), начиная с 9, будет 13 программ.

Для числа 17 получается ответ 169.

Ответ: 169

Источник