Алгоритмы(1657 задач)
Структуры данных(279 задач)
Интерактивные задачи(17 задач)
Другое(54 задач)
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:
>A).
>B).
A>).
B>).
A>B).
B>A).
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полность наполняется.
Программа получает на вход три натуральных числа A, B, N, не превосходящих 104.
Необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров
в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.
Количество операций в алгоритме не должно превышать 105. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 105 операций.
Тесты к этой задаче закрытые.
3 5 1
>A A>B >A A>B
3 5 6
Impossible
Нынешняя задача состоит в расшифровке текстов Велулу. Основная проблема заключается в том, что в их алфавите нет пробелов. Поэтому все тексты слипаются в одну последовательность букв, которые сложно разобрать.
К счастью, археологи уже разработали проект словаря велульского языка. Конечно же они знают о том, что можно обработать последовательность букв на компьютере и получить слова, имея в своем распоряжении словарь. Однако, воспользовавшись таким методом они обнаружили, что огромное количество таких последовательностей почти для любого текста разумного размера. Они не знают, является ли это проблемой метода обработки или особенностью велульского языка. Поэтому они придумали другой метод, который базируется не только на словаре, но и на порядке частей речи в предложении.
Теперь у них был не только словарь, но и предположение о том, как предложение строится в велульском языке. Вам предстоит определить, сколькими способами можно разбить текст на слова, следуя этим правилам, и вывести один из примеров разбиения.
Вам будет дан словарь, правила построения предожений и текст для расшифровки. Для каждого слова определено, какой частью речи оно может быть.
Первая строка входного файла содержит числа \(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.