Страница: << 1 2 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова, a, ab и aba являются префиксами слова aba) другого. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.

Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac , abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.

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

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

Первая строка входного файла содержит два целых числа: n и k количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (1 ≤ n ≤ 100000, 0 ≤ k ≤ 200). Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает 106. Все слова различны.

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

На первой строке выходного файла выведите одно число m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k. Следующие m строк должны содержать выбранные слова.

Примеры
Входные данные
6 2
aba
bacaba
abacaba
baca
abac
caba
Выходные данные
3
aba
baca
caba
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

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

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

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

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

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

Примеры
Входные данные
ABC
Выходные данные
ABC
Входные данные
O2A3O2AO
Выходные данные
OAAOOOAAO
Входные данные
A2B3C4D5E6F7G
Выходные данные
ABBCCCDDDDEEEEEFFFFFFGGGGGGG
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дано множество строк W. Необходимо найти минимальное множество строк X, такое, что путем конкатенации строк мн-ва X можно составить то же мн-во, что и путем конкатенации строк W

Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.

Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

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

Входной файл состоит из набора строк, каждая из которых является элементом множества \(W\). Каждая строка из множества \(W\) встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит \(10^4\). Количество строк во входном файле не превосходит \(10^4\). После каждой строки из множества \(W\) во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.

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

Выведите в выходной файл элементы одного из множеств \(X\), удовлетворяющих условиям задачи. Каждая строка множества \(X\) должна быть выведена ровно один раз. Строки должны идти в лексикографическом порядке (лексикографический порядок используется в словарях, в этом порядке строка `ab' меньше строки `aba' и строка `ab' меньше строки `ac'). После каждой строки множества \(X\) должен идти один перевод строки.

Примеры
Входные данные
a
aabb
ab
ac
b
bac
Выходные данные
a
ac
b

Строки формируются по правилу: S1 = a, Si = Si-1 + chr(i) + Si-1. Необходимо по данной строке найти максимальное i, такое что данная строка является подстрокой Si

Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .

После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.

Астрономы (в знак благодарности) нашли какую-то отдалённую звезду с огромной статуей динозавра, похожего на земные аналоги. Экспедиция, посетившая указанную звезду, нашла под статуей надпись, очевидно, с кодом этого динозавра. Впрочем, часть надписи стёрлась. Теперь учёные хотят максимально завысить древность находки. Для этого нужно определить, в коде динозавров какой эпохи – самой древней из подходящих – встречается данный образец (как подстрока). Такую задачу не по силам решить даже астрономам.

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

На первой и единственной строке входного файла находится непустая строка, состоящая из символов `a', …, `z', `0', …, `9'. Длина строки не превосходит 100.

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

Выведите два числа – номер эпохи и смещение образца от начала кода. Если же статуя изображает неземного динозавра (или код инопланетян отличается от земного), выведите в выходной файл число 0.

Примеры
Входные данные
a
Выходные данные
1 0
Входные данные
bae
Выходные данные
5 13
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Пара файлов называется тестом, если они находятся в одном каталоге и имеют полные имена вида «XY» и «XY.a», где «XY» — номер теста (дополненный ведущим нулем, если он меньше десяти). В первом из указанных файлов хранятся входные данные, а во втором — эталонный ответ.

Каталог называется каталогом с тестами, если в нем есть тесты со всеми номерами от \(1\) до \(N\), где \(1 \le N \le 99\), а других файлов нет (но могут быть подкаталоги).

Каталог называется задачей, если в нем есть файл с именем «check» и любым (возможно пустым) расширением и подкаталог «tests», который является каталогом с тестами. В каталоге-задаче помимо этого могут быть другие файлы и подкаталоги.

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

Задано описание всех файлов, хранящихся на жестком диске Вовиного компьютера. Необходимо найти, сколько описаний соревнований содержится на его жестком диске.

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

Первая строка входного файла содержит \(n\) — число файлов (\(1 \le n \le 1000\)). Каждая из последующих \(n\) строк содержит полный путь к файлу. Каждая из этих строк содержит от одного до 200 символов.

Элементы пути разделены символами «\». В начале элемента пути идет буква диска (от «A» до «Z»), затем следует двоеточие, затем «\». Имена каталогов в пути и имена файлов состоят из символов с кодами от 33 до 126, за исключением символа «\». Последний элемент пути является полным именем файла. Полное имя файла содержит не более одной точки, при этом до и после точки идет хотя бы один символ. Если имя файла содержит точку, то часть имени после точки называется расширением, а часть до точки — именем файла. Иначе считается, что файл имеет пустое расширение, а имя файла совпадает с его полным именем.

Строчные и заглавные буквы в путях не различаются. Ни в каком каталоге нет файла и подкаталога, имеющих одинаковые имена.

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

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

Примеры
Входные данные
22
C:\olymp\roi2005\aplusb\tests\01
C:\olymp\roi2005\aplusb\tests\01.a
C:\olymp\roi2005\aplusb\tests\02
C:\olymp\roi2005\aplusb\tests\02.a
C:\olymp\roi2005\aplusb\check.exe
C:\olymp\roi2005\gcd\tests\01
C:\olymp\roi2005\gcd\tests\01.a
C:\olymp\roi2005\gcd\tests\02
C:\olymp\roi2005\gcd\tests\02.a
C:\olymp\roi2005\gcd\check.cpp
C:\olymp\roi2005\gcd\solution.exe
C:\olymp\roi2006\aplusb\tests\01
C:\olymp\roi2006\aplusb\tests\01.a
C:\olymp\roi2006\aplusb\tests\03
C:\olymp\roi2006\aplusb\tests\03.a
C:\olymp\roi2006\aplusb\check.exe
C:\olymp\roi2006\gcd\tests\01
C:\olymp\roi2006\gcd\tests\01.a
C:\olymp\roi2006\gcd\tests\03
C:\olymp\roi2006\gcd\tests\02.a
C:\olymp\roi2006\gcd\check.cpp
C:\olymp\roi2006\gcd\solution.exe
Выходные данные
1

Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест