#3004

Разбиения на k слагаемых

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

Для данных натуральных чисел n и k определите количество способов представить число n в виде суммы k натуральных слагаемых, если способы, отличающиеся только порядком слагаемых считать одинаковыми.

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

Программа получает на вход два натуральных числа n и k, не превосходящих 150. Гарантируется, что ответ не превосходит 2³¹-1.

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

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

Примечание

Эту задачу разрешается (и рекомендуется) решать, при помощи Memorization.

Примеры

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

6 3

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

#3005

Количество правильных скобочных последовательностей

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

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

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

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

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

Необходимо вывести остаток от деления числа искомых последовательностей на 10⁹+7.

Примеры

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

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

#3007

Количество ПСП, вложенности k

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

По данным числам n и k определите количество правильных скобочных последовательностей длины 2n, составленных из круглых скобок, максимальная вложенность скобок в которой составляет в точности k.

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

Программа получает на вход два натуральных числа n и k (1≤k≤n≤50).

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

Необходимо вывести остаток от деления числа искомых последовательностей на 10⁹+7.

Примеры

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

3 1

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

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

3 2

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

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

3 3

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

#3088

Золотые слитки

Темы: [Задача о рюкзаке]

Даны N золотых слитков известных масс. Определите, какую наибольшую массу золота можно унести, если вместимость рюкзака не превышает S.

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

Программа получает на вход целое число S — вместимость рюкзака, не превосходящее 10000 и количество слитков N, не превосходящее 300. Далее следует N целых неотрицательных чисел, не превосходящих 100000 — веса слитков.

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

Программа должна вывести единственное целое число — максимально возможных вес золота, который поместится в данный рюкзак.

Примеры

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

10 3
5 7 4

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

#3089

Рюкзак

Темы: [Задача о рюкзаке]

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

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

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

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

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

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

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

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

Выведите одно целое число: наибольшую возможную стоимость рюкзака.

Примеры

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

4 6
2 4 1 2
7 2 5 1

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