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

A: Последовательности из 0 и 1 без двух единиц подряд

Вводится натуральное число N (до 50). Напишите программу, которая вычислит количество последовательностей длины N, состоящих из символов 0 и 1, в которых не встречается двух единиц подряд.

Например, для N=3 таких последовательностей 5:

Ввод	Вывод
3	5

B: Последовательности из 0, 1 и 2 без двух двоек подряд

Вводится натуральное число N (до 50). Напишите программу, которая вычислит количество последовательностей длины N, состоящих из символов 0, 1 и 2, в которых не встречается двух двоек подряд.

Например, для N=2 таких последовательностей 8:

Ввод	Вывод
2	8

C: Почти задача из ЕГЭ - 1

В Демо-версии ЕГЭ-2020 есть задача номер 22, которая звучит почти так:

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

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

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

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

Участникам ЕГЭ нужно решить задачу для конкретных чисел на бумажке (там есть еще одно дополнительное условие). А мы с вами будем писать программу.

Вам вводится натуральное число N (не больше 50). Надо посчитать, сколько существует различных программ, которые из числа 1 получают число N.

Например, программ, которые из 1 получают число 5 - 4 штуки:

Ввод	Вывод
5	4

D: Почти задача из ЕГЭ - 2

Вероятно, вы уже прочитали и решили предыдущую задачу. Если нет - начните с нее. Эта задача отличается дополнительным условием.

Вам вводится натуральное число N (не меньше 11, и не больше 50). Надо посчитать, сколько существует различных программ, которые из числа 1 получают число N, и при этом траектория вычислений не содержит число 10.
Траектория вычислений - это последовательность результатов выполнения всех команд программы. Например, для программы 121 (121 - это программа, то есть "+1", "*2", "+1") при исходном числе 1 траектория будет состоять из чисел 2, 4, 5.

Ввод	Вывод
11	0
12	6
20	32

E: Собственно задача из ЕГЭ - 3

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

Ввод	Вывод
11	14
12	14
20	28

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

На клеточках написаны натуральные числа. Лягушка находится в самой левой клетке и хочет попасть в самую правую. За один ход она может прыгнуть на одну, две или три клетки вправо (в первом случае из клетки X она попадет в клетку X+1, во втором X+2, в третьем X+3).

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

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

Выведите одно число - сколько придется заплатить лягушке.

Ввод	Вывод
1 3 5 25 25 4	10

G: Валютные махинации

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

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

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

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

Формат входных данных. Первая строка содержит одно число N (1<N<5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки.

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

Ввод	Вывод
4 1 10 10 5.53 5.53 1.25 6 5	4000.00

H: Последовательности из 0 и 1 без трех единиц подряд

Вводится натуральное число N (до 50). Напишите программу, которая вычислит количество последовательностей длины N, состоящих из символов 0 и 1, в которых не встречается трех единиц подряд.

Например, для N=3 таких последовательностей 7:

Ввод	Вывод
3	7