eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Алфавитный указатель

Алфавитный указатель

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

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

Будем считать, что в документе некого текстового процессора поля описываются следующим образом:

  • поле заключается в фигурные скобки;

  • после открывающейся фигурной скобки следует символ "/";

  • после символа "/" указывается тип поля в виде любого символа, отличного от пробела;

  • вся информация после символа кода поля до закрывающейся фигурной скобки считается текстом поля. Гарантируется, что текст поля не имеет пробелов и состоит, как минимум, из одной буквы;

  • если поле расположено внутри строки, то после него располагается, как минимум, один пробел.

Таким образом, признаком начала поля служит комбинация символов "{/". Например, правильное описание поля может иметь вид: {/AПример}.

Одним из видов полей являются поля для формирования алфавитного указателя. Будем считать, что кодом такого поля является символ "Z". Алфавитный указатель представляет собой информацию о встречающихся в документе терминах с указанием номеров страниц, на которых эти термины встречаются.

Алфавитный указатель формируется из полей с кодом "Z" по следующим правилам:

  • все термины сортируются в алфавитном порядке;

  • после термина через пробел указывается номер страницы, на которой он встречается;

  • если термин встречается на нескольких страницах, то страницы выводятся в порядке возрастания через комбинацию символов "запятая+пробел";

  • если термин встречается на странице несколько раз, то для данного термина номер этой страницы указывается только один раз;

  • все термины разбиваются на группы по первому символу. Символ группы выводится перед группой в отдельной строке;

  • большие и маленькие буквы считаются различными.

Пример алфавитного указателя:

ААрбуз 12, 48Аспирин 34ППродавец 73ЯЯблоко 2

Пусть дан текст, состоящий из слов с вставленными в него полями разного типа (границей слова является пробел, начало и конец строки). Считается, что поле расположено на той же странице, что ближайшее, расположенное перед ним, слово.

Требуется разбить заданный текст на строки и страницы по следующему правилу:

  • строка включает не более S символов, разбиение осуществляется по границам слов, в строке должно быть как можно больше слов, пробелы в начале и конце строки удаляются, между словами должно быть ровно по одному пробелу;

  • страница содержит N строк, пустых строк не может быть;

  • поля считаются невидимыми, т.е. при разбиении текста на строки и страницы все поля удаляются,

и для полученного текста построить предметный указатель.

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

Первая строка содержит два целых числа S и N, разделенных пробелом – максимальное количество символов в строке и количество строк на странице, соответственно (10S100, 1N100).

Последующие строки содержат исходный текст. Количество строк текста не более 1000. Длина строки не более200. Гарантируется, что в отформатированном тексте нет слов, имеющих длину более S. Гарантируется, что перед первым полем есть хотя бы одно слово. Гарантируется, что в тексте есть хотя бы одно поле с кодом "Z".

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

Выходной файл должен содержать алфавитный указатель, сформированный по указанным выше правилам.

Пример

Входные данные #1
15 2
��� ������{/Z������} � �����
"��������� ��������",{/Z��������}
�� ������ �������� ���������� ����������
����������� ��������.{/Z��������}
Выходные данные #1
�
������ 1
�
�������� 2, 5

Примечание

После разбиения исходного текста на строки и страницы он будет иметь вид:

Это пример к 1 страница

задаче

"Алфавитный 2 страница

указатель", на

основе которого 3 страница

показывается

построение 4 страница

алфавитного

указателя. 5 страница

Источник Региональная олимпиада по программированию, СибГИУ, 2011