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

Под ёлкой лежит N подарков в ряд. Известна радость, которую принесёт каждый подарок. По традиции Простоквашино, нельзя брать два соседних подарка — это невежливо. Дядя Фёдор хочет выбрать подарки так, чтобы суммарная радость была максимальной.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 1 до 1000 — радость от каждого подарка.

Выходные данные: Максимальная суммарная радость.

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


Входные данные

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

Выходные данные

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

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

Входные данные
Одно число 1≤N≤20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, AC, BA, BB, BC, CA, CB и CC. Стопки типа AA являются взрывоопасными.

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

Входные данные
Одно число 1 ≤ N ≤ 20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

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

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

Выходные данные
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹ − 1.

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

• creature[1] = 1
• creature[2 * i] = creature[i], если  2 <= 2 * i <= n
• creature[2 * i + 1] = creature[i] + creature[i + 1], при  2 <= 2 * i + 1 <= n

Чтобы понять, насколько могущественны существа в лесу, необходимо найти существо с максимальным уровенем энергии.


Входные данные
Программа получает на вход натуральное число n (1 <= n <= 100) - количество существ в фантастическом лесу.

Выходные данные
Выведите максимальный уровень энергии среди всех существ в данном фантастическом лесу.
 
 

Примеры

№	Входные данные	Выходные данные
1	1	1
2	7	3
3	3	2

 

Примеры

№	Входные данные	Выходные данные
1	1
2	5	121
3	562340	3333312222122213312

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

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

Примеры

№	Входные данные	Выходные данные
1	3 10 15 20	15 2
2	10 1 100 1 1 1 100 1 1 100 1	6 1 3 5 7 8 10

Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте i написана плата cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.

Формат входных дынных
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Формат выходных дынных
Выведите одно число - ответ на задачу.

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

Выходные данные
Выведите значение T_n.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).

 

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

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

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

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

Примеры

№	Входные данные	Выходные данные
1	2	2
2	3	3

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

№	Входные данные	Выходные данные
1	2	1
2	3	2
3	4	3

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

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

№	Входные данные	Выходные данные
1	2	2
2	3	3

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

Выходные данные
Выведите значение T_n.
 
 

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры

№	Входные данные	Выходные данные
1	2	1
2	3	2
3	4	3

Примеры

№	Входные данные	Выходные данные
1	2	2
2	5	4

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

Входные данные

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

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	4	7

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки. 
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

Определите, какое наименьшее число туров необходимо отыграть для того, чтобы получить из 1 заданное число баллов N.

Входные данные

Программа получает на вход одно число, не превосходящее 10⁶.

Выходные данные

Требуется вывести одно число: наименьшее количество искомых операций.

 

 

Примеры

№	Входные данные	Выходные данные
1	1	0
2	5	3
3	32718	17

 

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

Входные данные

На вход программы поступает целое число N  (\(1<=N<=100\) ).

Выходные данные

Выведите ответ на задачу.

 

 

Примеры

№	Входные данные	Выходные данные
1	1	2

 

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.

Входные данные

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

Выходные данные

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

 

 

Примеры

№	Входные данные	Выходные данные
1	4	7