Страница: << 47 48 49 50 51 52 53 >> Отображать по:

#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.

#3674

Игра на бирже

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

#3711

Большой, белый, очень прямоугольный

Темы: [Двумерные массивы] [Динамическое программирование на таблицах] [Стек]

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

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

Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.

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

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

Примеры

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

5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0

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

#3712

Логическое дерево

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

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

Каждая вершина дерева имеет связанное с ней логическое значение (1 или 0). Кроме этого, каждая внутренняя вершина имеет связанную с ней логическую операцию („И“ или „ИЛИ“). Значение вершины с операцией „И“ — это логическое „И“ значений её детей. Аналогично, значение вершины с операцией „ИЛИ“ — это логическое „ИЛИ“ значений её детей. Значения всех листьев задаются во входном файле, поэтому значения всех вершин дерева могут быть найдены.

Наибольший интерес для нас представляет корень дерева. Мы хотим, чтобы он имел заданное логическое значение \(v\), которое может отличаться от текущего. К счастью, мы можем изменять логические операции некоторых внутренних вершин (заменить „И“ на „ИЛИ“ и наоборот).

Дано описание логического дерева и набор вершин, операции в которых могут быть изменены. Найдите наименьшее количество вершин, которые следует изменить, чтобы корень дерева принял заданное значение \(v\). Если это невозможно, то выведите строку «IMPOSSIBLE» (без кавычек).

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

В первой строке входного файла находятся два числа \(n\) и \(v\) (\(1 \le n \le 10\,000, 0 \le v \le 1\)) — количество вершин в дереве и требуемое значение в корне соответственно. Поскольку все вершины имеют ноль или двоих детей, то \(n\) нечётно. Следующие \(n\) строк описывают вершины дерева. Вершины нумеруются от \(1\) до \(n\).

Первые \((n-1)/2\) строк описывают внутренние вершины. Каждая из них содержит два числа — \(g\) и \(c\), которые принимают значение либо \(0\), либо \(1\). Если \(g=1\), то вершина представляет логическую операцию „И“, иначе она представляет логическую операцию „ИЛИ“. Если \(c=1\), то операция в вершине может быть изменена, иначе нет. Внутренняя вершина с номером \(i\) имеет детей \(2i\) и \(2i+1\).

Следующие \((n+1)/2\) строк описывают листья. Каждая строка содержит одно число \(0\) или \(1\) — значение листа.

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

В выходной файл выведите ответ на задачу.

Примеры

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

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

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

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

IMPOSSIBLE

#3717

Числа

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

Дана последовательность чисел a₁, a₂, ..., a_n. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Пример начальной последовательности:

1 50 51 50 1

удаляем четвертое число, штраф 50·(1 + 51) = 2600, получаем

1 50 51 1

удаляем третье число, штраф 51·(50 + 1) = 2601, получаем

1 50 1

удаляем второе число, штраф 50·(1 + 1) = 100.

Итого, штраф 5301.

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

В первой строке входного файла расположено одно число n (1 ≤ n ≤ 100) — количество чисел в последовательности.

Во второй строке находятся n целых чисел a₁, a₂, ... a_n; никакое из чисел по модулю не превосходит 100.

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

Выведите в выходной файл одно число — минимальный суммарный штраф.

Примеры

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

5
1 50 51 50 1

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

Страница: << 47 48 49 50 51 52 53 >> Отображать по:

Выбрано

Отменить

Добавить в контест