Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 376 377 378 379 380 381 382 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

  1. Наполнить сосуд A (обозначается >A).
  2. Наполнить сосуд B (обозначается >B).
  3. Вылить воду из сосуда A (обозначается A>).
  4. Вылить воду из сосуда B (обозначается B>).
  5. Перелить воду из сосуда A в сосуд B (обозначается как A>B).
  6. Перелить воду из сосуда B в сосуд A (обозначается как B>A).

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

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

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

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

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

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

Тесты к этой задаче закрытые.

Примеры
Входные данные
3
5
1
Выходные данные
>A
A>B
>A
A>B
Входные данные
3
5
6
Выходные данные
Impossible
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Мистер Форд Транкингс, известный археолог, недавно обнаружил в самом сердце Африки остатки загадочного поселения. Через несколько недель исследования он и его коллеги поняли, что они нашли нечто необычное. Племена Велулу, которые жили там 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.

Страница: << 376 377 378 379 380 381 382 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест