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

Кузнечик-KMax#27081

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

Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю \(10^6 + 7\) , то есть найдите остаток от деления этого числа на \(10^6 + 7\) .

Входные данные: входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что \(1 <= N ,\ K <= 10000\).

Выходные данные: программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю \(10^6+7\).

Примеры

№	Входные данные	Выходные данные
1	10 5	236
2	100 50	934384

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

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

Кузнечик-K#27080

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

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .

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

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

Ввод	Вывод
5 4	8

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

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

Кузнечик#27079

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

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

Входная строка содержит натуральное число N ( 1 ≤ N ≤ 45 ).

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

Ввод	Вывод
3	2
10	55

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

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

Кузнечик собирает монеты#27069

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

Входные данные
- в первой строке вводятся два натуральных числа: N и K (\(2 <= N ,\ K <= 10000\)), разделённые пробелом;
- во второй строке записаны через пробел N-2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты.
Гарантируется, что все числа по модулю не превосходят 10000.

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

- в первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик;
- во второй строке выводится число прыжков Кузнечика;
- в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

Если правильных ответов несколько, выведите любой из них.

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

✓ 404✗ 1 223700средняяВойти и решать

Обход по графу. Построение дерева решений#27035

Разработан шифр, при использовании которого каждой цифре ставится в

соответствие определенная буквенная последовательность как приведено в таблице.

1	2	3	4	5	6	7
AB	CB	CBA	ABC	BC	BBC	CCB

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

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

Ввод	Вывод
ABCCBABBCCBABC	6

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

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

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

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

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

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

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

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

✓ 2✗ 41 100средняяВойти и решать

Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

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

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

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

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

✓ 2✗ 371 100средняяВойти и решать

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

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

Пример

Ввод	Вывод
3	6

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

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

Это Бомба#24906

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

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

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

Постройка забора#24762

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

Забор представляет собой многоугольник ненулевой площади, сторонами которого являются доски. Пилить или ломать доски нельзя. Например, из трех досок с длинами 10, 11 и 12 можно построить забор, а из четырех досок с длинами 100, 1, 2 и 3 — нельзя.

У Деда нашлось целых n досок, поэтому они с Бабой задались вопросом: а сколько различных способов выбрать несколько досок из имеющихся, чтобы из них затем можно было построить забор? Способы считаются различными, если существует доска, которая используется в одном из них, но не используется в другом.

Пожилым людям надо помогать, так что вам не составит труда решить для них эту задачу! Количество способов может быть довольно большим, поэтому выведите остаток от деления этого количества на число 10⁹ + 7.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 4000) — количе- ство досок. Во второй строке дано n чисел li (1 ≤ l_i ≤ 4000) — длины досок.

Формат выходного файла
В выходной файл выведите одно число — количество способов выбрать доски для постройки забора, взятое по модулю 10⁹ + 7.

Ввод	Вывод
3 10 11 12	1
4 100 1 2 3	0
4 5 5 5 5	5

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

✓ 5✗ 441 100средняяВойти и решать

Пустоты в кубе#23588

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

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

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

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

Первая строка входного файла содержит целое число S (1<=S<=80).

В последующих строках записан отчет, содержащий не более 500 слов.

Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превос-ходит S.

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

Вывести в первую строку выходного файла минимально возможную сумму

кубов пустот по всем строкам. В последующие строки следует вывести

искомое расположение текста на листе бумаги.

Пример входного файла

Победители летних учебно-тренировочных сборов по информатике 1997 г.:

Владимир Мартьянов,

Анатолий Пономарев,

Николай Дуров,

Андрей Лопатин.

Пример выходного файла

325

Победители летних

учебно-тренировочных сборов по

информатике 1997 г.: Владимир

Мартьянов, Анатолий Пономарев,

Николай Дуров, Андрей Лопатин.

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

✓ 0✗ 11 300средняяВойти и решать

Покупка билетов#23414

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

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

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

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

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

Входные данные:
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел A_i, B_i, C_i. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.

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

Примеры

№	Входные данные	Выходные данные
1	5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1	12
2	2 3 4 5 1 1 1	4

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

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

Шаблон и слово#23413

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).

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

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

Примеры

№	Входные данные	Выходные данные
1	ABBCDA A*CDA	YES
2	AADAAVA ADAAA*	NO

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

✓ 5✗ 121 100средняяВойти и решать

Ход конем#23411

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Клавиатура телефона выглядит так:

7	8	9
4	5	6
1	2	3
	0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

Входные данные: на вход подается целое число N (\(1<=N<=50\)).

Выходные данные: выведите файл искомое количество телефонных номеров.

Примеры

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

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

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

Гвоздики#23408

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

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

- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

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

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

Число способов#22015

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

Посчитайте, сколько есть способов у игрока попасть в правую

нижнюю клетку.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,

1<=M<=10).

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

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

Примечание

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

Пример входного файла

2 3

Пример выходного файла

Пояснение

Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие

способы попасть из левого верхнего угла в правый нижний:

1) вниз, вправо, вправо

2) вправо, вниз, вправо

3) вправо, вправо, вниз

Еще один пример входного файла

3 3

Пример выходного файла

Динамическое программирование на таблицах Динамическое программирование: один параметр Комбинаторика

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

Кладовка из Простоквашино#21996

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

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_iминут.

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

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

Формат выходных данных
Выведите одно целое число — минимальное количество рублей, которое придётся потратить жителям дома, чтобы выполнить все запланированные визиты в кладовку при свете.

Ввод	Вывод
1 2 5 6 3 5	12
3 1 15 10 1 3 4 5 30 35	105

Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку

Динамическое программирование Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

✓ 13✗ 1651 000средняяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

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

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

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

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

✓ 2✗ 771 200средняяВойти и решать

Укладка плитки#21902

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹ + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток (1 ≤ n ≤ 100 000, 0 ≤ k < 2n). Последующие k строк содержат по два целых числа xi и yi , которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 7.

Ввод	Вывод
2 0	7
3 0	22
3 1 2 1	8

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

✓ 3✗ 11 200средняяВойти и решать

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лёгкаяВойти и решать