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

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

Её особенно заинтересовала игра, в которую она сейчас играет. Игра начинается с последовательности из N положительных целых чисел (2 ≤ N ≤ 262144), каждое из которых находится в диапазоне от 1 до 40. За один ход Бесси может взять два соседних числа с одинаковыми значениями и заменить их на одно число на единицу больше (например, она может заменить две соседние семёрки на восьмёрку). Цель состоит в том, чтобы максимизировать значение наибольшего числа в последовательности в конце игры. Пожалуйста, помогите Бесси набрать как можно больше очков.

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

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

Примечание
В приведенном здесь примере Бесси сначала объединяет вторую и третью единицы, чтобы получить последовательность 1 2 2, а затем объединяет двойки в тройку. Обратите внимание, что объединение первых двух единиц не является оптимальным.
 

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

Пример: в последовательности 5 8 13 9 17 12 21 25 можно выбрать:

• 5 9 17 21 25 или 5 13 17 21 25 (остаток 1 при делении на 4, длина 5)
• 8 12 (остаток 0 при делении на 4, длина 2)

Максимальная длина = 5.

Напишите программу, которая находит эту максимальную длину.

Формат входных данных

• В первой строке число n (1 ≤ n ≤ 20000)
• Во второй строке n чисел через пробел

Формат выходных данных

• Длина самой большой такой подпоследовательности

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться  до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

Два способа считаются различными, если последовательность прыжков отличается.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

В Простоквашино построили ледяную горку. Она состоит из N ступенек. На каждой ступеньке написано число — сколько секунд нужно отдохнуть, если встать на неё. Дядя Фёдор стартует перед первой ступенькой и может прыгать на 1 или 2 ступеньки вперёд. Ему нужно добраться до вершины (встать на последнюю ступеньку), потратив минимум времени на отдых.

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

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

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

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

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

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Известно, что 𝐴, 𝐵 и 𝐶 - натуральные числа и что 𝐴 < 𝐵 < 𝐶.
Петя вызывает эту функцию, передавая ей в качестве входного параметра натуральное число. Известно, что для некоторого 𝑘 функция возвращает следующие значения:
𝐹(𝑘) = 50890368413;
𝐹(𝑘 + 1) = 93601980590;
𝐹(𝑘 + 2) = 172160883161.
Определите значения 𝐴, 𝐵 и 𝐶, при которых это возможно. Если таких вариантов несколько, выберите вариант с наименьшей суммой 𝐴, 𝐵 и 𝐶. В ответе введите в указанном порядке значения 𝐴, 𝐵 и 𝐶, разделённые пробелом.
 

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

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

Примеры

№	Входные данные	Выходные данные
1	2023 2007	32248

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

• за одну операцию можно снять только 1 ле́токоин,

• за одну операцию можно снять сумму 6^x, где x  - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),

• за одну операцию можно снять сумму 9^x, где x  - любое натуральное число  (можно снять сумму равную 9, 81, 729, ...).

Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?

Примечание: невозможно повторно вносить снятые деньги в банк!

Формат входных данных
На вход подается целое число N (\(1<=N<=100000\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16