#3003

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

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

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

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

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

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

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

Примеры

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

5 3

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

#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

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

#3672

Форд Транкингс и язык Велулу

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

Мистер Форд Транкингс, известный археолог, недавно обнаружил в самом сердце Африки остатки загадочного поселения. Через несколько недель исследования он и его коллеги поняли, что они нашли нечто необычное. Племена Велулу, которые жили там 20 000 лет назад, по-видимому, достигли высокого уровня развития. У них даже был алфавит! Но большинство из них стало жертвой ледникового периода и все их културные достижения были утрачены. Только несколько счастливчиков из племени выжили и попытались возрадить исчезнувшую цивилизацию. Теперь они известны под именем грозных зусулов, но об этом в другой раз...

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

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

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

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

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

Первая строка входного файла содержит числа \(N\), \(M\) и \(K\), где \(1 \leq N \leq 5000\) — количество слов в велульском словаре, \(1 \leq M \leq 10\) — количество правил построения предожения, а \(1 \leq K \leq 10\) — количество различных частей речи.

В вельском языке не так много букв. Так что археологи закодировали их маленькими латинскими буквами. В каждой из \(N\) следующих строк содержится слово (не длиннее 20 символов), затем число \(k_i\) (\(1 \leq k_i \leq 10\)) — количество частей речи, которыми может быть это слово, а затем \(k_i\) чисел \(a_{ij}\) обозначающие допустимые части речи. Все числа \(a_{ij}\) даны в возрастающем порядке. Слова в словаре даны в произвольном порядке (не успели упорядочить). Каждое слово встречается в словаре только один раз.

Следующие \(M\) строк содержат правила конструирования предожений. Каждое правило описывается количеством слов в предложении \(l_i\) (\(1 \leq l_i \leq 10\)) и, затем, перечислены \(l_i\) чисел, являюзихся идентификаторами частей речи. Правила не повторяются.

Последняя строка ввода содержит текст, который надо расшифровать. Текст не пуст и его длина не превышает 1000 символов.

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

Первая строка должна содержать количество вариантов расшифровки. Если их больше чем \(10^{18}\) выведите строку «TOO MANY» вместо количества.

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

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

Примеры

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

5 2 2
ba 1 2
za 2 1 2
a 2 1 2
caba 1 1
ab 1 1
2 1 2
3 2 2 1
abazabacaba

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

2
a ba. za ba caba.

Страница: << 4 5 6 7 8 9 10 >> Отображать по: