--->
35 задач
<---
Источники
Нынешняя задача состоит в расшифровке текстов Велулу. Основная проблема заключается в том, что в их алфавите нет пробелов. Поэтому все тексты слипаются в одну последовательность букв, которые сложно разобрать.
К счастью, археологи уже разработали проект словаря велульского языка. Конечно же они знают о том, что можно обработать последовательность букв на компьютере и получить слова, имея в своем распоряжении словарь. Однако, воспользовавшись таким методом они обнаружили, что огромное количество таких последовательностей почти для любого текста разумного размера. Они не знают, является ли это проблемой метода обработки или особенностью велульского языка. Поэтому они придумали другой метод, который базируется не только на словаре, но и на порядке частей речи в предложении.
Теперь у них был не только словарь, но и предположение о том, как предложение строится в велульском языке. Вам предстоит определить, сколькими способами можно разбить текст на слова, следуя этим правилам, и вывести один из примеров разбиения.
Вам будет дан словарь, правила построения предожений и текст для расшифровки. Для каждого слова определено, какой частью речи оно может быть.
Первая строка входного файла содержит числа \(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.
Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.
К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.
Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.
Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100000.
Выведите соответствующий данному латинско-английский словарь, в точности соблюдая формат входных данных. В частности, первым должен идти перевод лексикографически минимального латинского слова, далее — второго в этом порядке и т.д. Внутри перевода английские слова должны быть также отсортированы лексикографически.
3 apple - malum, pomum, popula fruit - baca, bacca, popum punishment - malum, multa
7 baca - fruit bacca - fruit malum - apple, punishment multa - punishment pomum - apple popula - apple popum - fruit
Дана база данных о продажах некоторого интернет-магазина.
Каждая строка входного файла представляет собой запись вида
Покупатель товар количество, где
Покупатель — имя покупателя (строка без пробелов),
товар — название товара (строка без пробелов),
количество — количество приобретенных единиц
товара.
Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
Вводятся сведения о покупках в указанном формате. Количество не превосходит 10^9
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5
Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5
Как известно, в США президент выбирается не прямым голосованием, а путем двухуровневого голосования. Сначала проводятся выборы в каждом штате и определяется победитель выборов в данном штате. Затем проводятся государственные выборы: на этих выборах каждый штат имеет определенное число голосов — число выборщиков от этого штата. На практике, все выборщики от штата голосуют в соответствии с результами голосования внутри штата, то есть на заключительной стадии выборов в голосовании участвуют штаты, имеющие различное число голосов.
На этот раз вам известно число выборщиков от каждого штата США и результаты голосования каждого гражданина США (а также в каком штате проживает данный гражданин).
Вам необходимо подвести результаты голосования: сначала определить результаты голосования в каждом штате и определить, за какого из кандидатов отданы голоса выборщиков данного штата. Далее необходимо подвести результаты голосования выборщиков по всем штатам.
Первая строка входных данных содержит количество штатов в США N. Далее идет N строк, описывающих штаты США, каждая строка состоит из названия штата и числа выборщиков от этого штата. Далее до конца файла идут записи результатов голосования по каждому из участников голосования. Одна строка соответствует одному избирателю. Записи имеют вид: название штата, имя кандидата, за которого проголосовал данный избиратель. Названия штатов и имена кандидатов не содержат пробелов.
Выведите список кандидатов, упорядоченный по убыванию числа голосов выборщиков, полученных за данного кандидата, а при равенстве числа голосов выборщиков: в лексикографическом порядке. После имени кандидата выведите число набранных им голосов.
Если в каком-либо штате два или более число кандидатов набрали одинаковое число голосов, то все голоса выборщиков этого штата получает наименьший в лексикографическом порядке кандидат из числа победителей в этом штате.
Гарантируется, что в каждом штате проголосовал хотя бы один избиратель.
1. В Florida 2 избирателя голосует за Gore и три избирателя
за Bush, поэтому 25 голосов выборщиков от Floria получает Bush. В Pennsylvania
побеждает Gore (5 голосов против 1), поэтому Gore получает 23 голоса выборщиков от Pennsylvania.
2. В Florida побеждает Gore (5 голосов выборщиков), в Alaska — Bush (2 голоса выборщика). В Pennsylvania два кандидата набрали наибольшее число голосов (по 1), поэтому
4 голоса выборщиков от этого штата получает Clinton, т.к. он идет раньше в лексикографическом порядке.
2 Florida 25 Pennsylvania 23 Florida Gore Pennsylvania Gore Florida Bush Pennsylvania Gore Pennsylvania Bush Florida Gore Pennsylvania Gore Florida Bush Pennsylvania Gore Florida Bush Pennsylvania Gore
Bush 25 Gore 23
3 Florida 5 Pennsylvania 4 Alaska 3 Florida Gore Pennsylvania Obama Pennsylvania Clinton Alaska Bush
Gore 5 Clinton 4 Bush 3 Obama 0
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.
Вам дано генеалогическое древо, определите высоту всех его элементов.
Программа получает на вход число элементов в генеалогическом древе \(N\). Далее
следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника.
Каждая строка имеет вид имя_потомка имя_родителя.
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
Эта задача имеет решение сложности \(O(n)\), но вам достаточно написать решение сложности \(O(n^2)\) (не считая сложности обращения к элементам словаря).
Пример ниже соответствует приведенному древу рода Романовых.
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I
Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2