• Document: Одномерное динамическое программирование
  • Size: 220.63 KB
  • Uploaded: 2019-01-13 16:39:49
  • Status: Successfully converted


Some snippets from your converted document:

Динамическое программирование. Вводные задачи A. Мячик на лесенке На вершине лесенки, содержащей 𝑁 ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переме- ститься на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю. Вводится одно число 0 < 𝑁 < 31. Выведите одно число — количество маршрутов. Input Output 4 7 B. Последовательность из 0 и 1 Требуется подсчитать количество последовательностей длины 𝑁 , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом. На вход программы поступает целое число 𝑁 (1 6 𝑁 6 105 ). Выведите количество искомых последовательностей по модулю 109 + 7. Input Output 1 2 C. Без трёх единиц Определите количество последовательностей из нулей и единиц длины 𝑁 (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом. Вводится натуральное число 𝑁 , не превосходящее 40. Выведите количество искомых последовательностей. Гарантируется, что ответ не превос- ходит 231 − 1. Input Output 3 7 D. Платная лестница Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно за- платить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадо- бится мальчику, чтобы добраться до верхней ступеньки. В первой строке входного файла вводится одно натуральное число 𝑁 6 100 — количество ступенек. В следующей строке вводятся 𝑁 натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх). Выведите одно число — наименьшую возможную стоимость прохода по лесенке. Input Output 3 2 1 3 1 Одномерное динамическое программирование E. Радиоактивные материалы При переработке радиоактивных материалов образуются отходы трех видов — особо опас- ные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладывают- ся вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопас- ной. Для заданного количества контейнеров 𝑁 определить число безопасных стопок. На вход программе подаётся одно число 1 6 𝑁 6 105 . Программа должна вывести одно число — количество безопасных вариантов формирова- ния стопки, взятое по модулю 109 + 7. Input Output 2 8 F. Поход вдоль реки Дети пошли в поход вдоль реки. Поход начинается на левом берегу, заканчивается на пра- вом. Дана по

Recently converted files (publicly available):