#3086

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

Дано натуральное число N. Необходимо представить его в виде суммы точных кубов, содержащей наименьшее число слагаемых. Программа должна вывести это число слагаемых.

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

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

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

Программа должна вывести единственное натуральное число.

Примеры

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

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

#3087

Банкомат

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

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

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

Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x₁, x₂, ..., x_N, не превосходящих 10⁶ — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10⁶ —сумму, которую необходимо выдать.

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

Программа должна найти представление числа S виде суммы слагаемых из множества x_i, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.

Примеры

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

5
1 3 7 12 32
40

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

32 7 1

#3297

Поход (10-11)

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

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2011, Задача D ]

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

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

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

Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит \(10^5\) символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

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

Выведите одно целое число - минимальное количество переправ.

Примечания

Рисунок к приведенному выше примеру.

Примеры

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

LLBLRRBRL

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

#3385

Министерство правды

Темы: [Динамическое программирование: один параметр] ["Два указателя"]

#3387

Обратный кузнечик

Темы: [Простые числа и разложение на множители] [Динамическое программирование: один параметр]