Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

MTN DEW#21780

Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.

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

На вход подается число n (0 <= n <= 70).

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

Выведите одно число - полученный скилл.

Примеры

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

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo.

Динамическое программирование Динамическое программирование: один параметр Рекуррентные последовательности

✓ 296✗ 741500лёгкаяВойти и решать

Фишки-палочки#47746

Алиса и Громозека играют в фишки-палочки. У каждого из них есть набор фишек, на каждой фишке записано одно целое число. Каждый из них выкладывает свои фишки вдоль двух параллельных горизонтальных линий. Следующим шагом Алиса соединяет палочкой две фишки, расположенные на разных горизонтальных линиях, то есть соединяет одну свою фишку с одной из фишек Громозеки по следующим правилам:

числа, на фишке Алисы и на фишке Громозеки равны;
соединяющая палочка не должна пересекать другие палочки;
две палочки не могут указывать на одну и ту же фишку.

Далее, Громозека считает сколько палочек выложила Алиса. После этого, Алиса убирает свои палочки и фишки соединяет Громозека по тем же правилам. Выигрывает тот, кто выложит по данным правилам больше всего палочек.

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

Входные данные
Первая строка входных данных содержит число n - количество фишек Алисы. Вторая строка содержит n чисел nums1_i - числа на фишках Алисы, в том порядке, в котором она их выложила. Третья строка содержит число m - количество фишек Громозеки. Четвертая строка содержит m чисел nums2_j - числа на фишках Громозека, в том порядке, в котором он их выложил.

Ограничения

1 <= n, m <= 500
1 <= nums1[i], nums2[j] <= 2000

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

Примечание
Рисунок к первому тестовому примеру

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

✓ 45✗ 47600лёгкаяВойти и решать

Айвен собирает кристаллы#47744

Юный волшебник Айвен отправляется в волшебный лес, чтобы набрать волшебных кристаллов. Каждый кристалл, растущий в данном лесу, обладает своей массой. Айвен имеет рюкзак, который может выдержать определенный вес M. Айвен хочет использовать свой рюкзак по максимуму и набрать кристаллов такое количество, чтобы суммарно их вес равнялся в точности весу, который может выдержать его рюкзак.
Вам стали известны массы кристаллов, которые растут в волшебном лесу. Выведите "YES", если Айвен сможет набрать кристаллов суммарным весом ровно M, иначе выведите "NO".

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10⁴. Во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные
Выведите YES или NO.

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

✓ 37✗ 60600лёгкаяВойти и решать

Магическая подпоследовательность Айвена#47742

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

Входные данные
Программа получает на вход последовательность символов s (1<= |s| <= 1000), состоящую из строчных английских букв.

Выходные данные
Выведите одно число - длину самой длинной магической подпоследовательности.

Примеры

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

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

✓ 34✗ 24500лёгкаяВойти и решать

Кристаллы максимуса#47675

Максимус очень любит коллекционировать кристаллы. Среди всех кристаллов у него есть один самый любимый с магической силой равной n. Также у него есть коллекция совершенных кристаллов. Совершенный кристалл - это кристалл, магическая сила которого равна квадрату натурального числа.
У Максимуса выдался свободный вечер, и он задумался: сколько нужно ему совершенных кристаллов, чтобы сумма их магических сил равнялась бы магической силе его любимого кристалла?
Квадратом натурального числа является число, которое получается умножением натурального числа на себя. Например, 1, 4 и 9 - это квадраты натуральных чисел, а 2, 3 и 5 - нет.
Ваша задача - помочь Максимусу найти минимальное количество совершенных кристаллов, сумма магических сил которых равна n.

Входные данные
Программа получает на вход натуральное число n (n < 10⁴).

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	12	3	`12 = 4 + 4 + 4`
2	`13`	`2`	`13 = 4 + 9`

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

✓ 40✗ 71500лёгкаяВойти и решать

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

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

Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.

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

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

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

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

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

Примеры

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

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

✓ 436✗ 1 069600лёгкаяВойти и решать

Маршрут наименьшей стоимости#46697

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

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

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

✓ 504✗ 1 093600лёгкаяВойти и решать

Стоимость проезда#46622

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

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

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

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

✓ 985✗ 995500лёгкаяВойти и решать

N-е число Трибоначчи (снизу-вверх)#46621

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

T₀ = 0, T₁ = 1,
T₂ = 1, и T_n+3 = T_n + T_n+1 + T_n+2 при n >= 0.

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

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

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

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

Примеры

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

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

✓ 773✗ 725300лёгкаяВойти и решать

Подняться на вершину горы (рекурсивно)#46620

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

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

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

Примеры

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

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

✓ 648✗ 987400лёгкаяВойти и решать

Числа Фибоначчи. Динамика снизу вверх#46619

Числа Фибоначчи, обозначаемые обычно 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

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

✓ 730✗ 1 322300лёгкаяВойти и решать

Подняться на вершину горы (снизу-вверху)#46618

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

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

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

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

Примеры

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

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

✓ 733✗ 700300лёгкаяВойти и решать

N-е число Трибоначчи (рекурсивно)#46617

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

T₀ = 0, T₁ = 1,
T₂ = 1, и T_n+3 = T_n + T_n+1 + T_n+2 при n >= 0.

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

Примеры

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

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

✓ 724✗ 1 601400лёгкаяВойти и решать

Числа Фибоначчи: Мемоизация рекурсии (Python)#46616

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

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

✓ 701✗ 1 427400лёгкаяВойти и решать

Сдача (java)#46546

Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль.

Например, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Входные данные
На вход программе подается натуральное число n <= 100 — размер сдачи, которую необходимо выплатить.

Выходные данные
Выведите искомое количество способов выплаты.

Примеры

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

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

✓ 124✗ 12300лёгкаяВойти и решать

Мячик на лесенке#38639

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

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

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

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

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

Примеры

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

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 211✗ 205400лёгкаяВойти и решать

Числа Фибоначчи: Мемоизация рекурсии (C++)#33688

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

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

Примеры

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

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

✓ 373✗ 826700средняяВойти и решать

Небоскреб#31785

В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.

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

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

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

Программа получает на вход количество этажей в небоскребе n.

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

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

Примечание

Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.

Подсказки

1. Как следует действовать, если шарик был бы только один?

2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?

3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.

Примеры

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

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 61✗ 110700средняяВойти и решать

Опасные отходы#27085

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

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

Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).

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

Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

Примеры

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

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 88✗ 156700средняяВойти и решать

Зоомагазин-2#27084

В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

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

Программа должна вывести количество безопасных способов расстановки N клеток в ряд.

Ввод	Вывод
5	16

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

✓ 49✗ 23700средняяВойти и решать