--->
45 задач
<---
Источники
Вот уже три года майор Пронин ведёт борьбу с подпольной группой по производству контрафактной продукции. Недавно его коллега, внедрившийся под прикрытием в эту организацию, передал ему важнейший документ, описывающий местонахождение главной фабрики преступников. К несчастью, сразу после этого он был раскрыт.
Майор понимал, что у него совсем немного времени до того, как придут и за ним. Поэтому он выбрал некоторый кусок документа и переслал Вам, своему ближайшему соратнику по борьбе со злом (майор боялся, что не хватит времени отправить документ целиком). Сразу после этого к нему ворвались злоумышленники и схватили Пронина. Чтобы не вызывать никаких подозрений, преступники решили не удалять документ, а просто закодировать его некоторым образом. Известно лишь, что каждый символ был заменён ровно на один символ, при этом разные символы перешли в разные, одинаковые – в одинаковые. Известно, что и до, и после перекодировки документ состоял только из символов с ASCII-кодами от 32 до 255 включительно.
Получив часть документа S, Вы немедленно отправились выручать Пронина из беды, но его дом оказался пуст. На его компьютере остался закодированный документ. Ни майор, ни его коллега на связь не выходят. Вы поняли, что единственный способ отыскать их – проникнуть на главную фабрику организации. Для этого необходимо раскодировать весь документ. Прежде чем передать его лингвистам, нужно произвести техническую обработку.
Возможно, что в тексте есть несколько фрагментов, которые могут являться кодом имеющегося у вас фрагмента S. Вы наудачу предположили, что имеющийся у вас фрагмент S в закодированном тексте является самым первым из фрагментов, в которые он мог быть закодирован.
Ваша задача – вычислить, какие символы документа могут быть определены однозначно исходя из приведённых соображений.
В первой строке записан перекодированный документ, во второй – часть документа S, оказавшаяся у вас. Обе строки имеют длину не более 106 символов и состоят только из символов с ASCII-кодами от 32 до 255 включительно. Длина S меньше длины документа.
Если на каком-то этапе произошла ошибка и входные данные некорректны, выведите Impossible. Иначе запишите в первой строку Possible, а во вторую – результат раскодировки. Символы, которые невозможно определить однозначно, замените на ?.
Подзадача 0 (0 баллов) тесты из условия.
Подзадача 1 (30 баллов) Обе строки состоят только из латинских маленьких букв. Длина каждой строки не превосходит 100. Балл за группу начисляется при прохождении всех тестов группы.
Подзадача 2 (30 баллов) Длина каждой строки не превосходит 1000. Балл за группу начисляется при прохождении всех тестов группы.
Подзадача 3 (40 баллов) Без дополнительных ограничений. В подгруппе 8 тестов каждый из которых оценивается в 5 баллов.
ababc ab
Possible abab?
fadacabba bcc
Possible ?b?b?bccb
abcdef ee
Impossible
cdcd ab
Possible abab
Вова проводит соревнования и тренировки по программированию в своей школе. Для этого он скачал из Интернета много архивов разных соревнований и сборов по программированию. Он разархивировал все, что скачал, на жесткий диск своего компьютера, и теперь не может разобраться в получившемся наборе файлов. Вова хочет понять, сколько описаний соревнований по программированию он скачал.
Пара файлов называется тестом, если они находятся в одном каталоге и имеют полные имена вида «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
Недавно разведка перехватила зашифрованное сообщение — строку s. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование. Ваш отдел занимается шифрами нового поколения. На данный момент известно всего n таких шифров. Для каждого из них есть три характерных параметра — целые числа l, r и строка t. Пусть строка g была получена в результате применения этого метода. Тогда строка glgl+1 . . . gr−1gr (здесь gi — это i-й символ строки g) содержит t как подстроку.
Вам поручено определить для каждого типа шифрования, могло ли сообщение s быть получено в результате его применения.
Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100 000, где |s| — длина строки s).
Вторая строка входного файла содержит целое число n — количество типов шифрования (1 ≤ n ≤ 100 000). Последующие nстрок содержат по два целых числа li, ri и строку ti, разделенные пробелами — характерные параметры i-го метода шифрования (1 ≤ li ≤ ri ≤ |s|).
Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех ti не превосходит 100 000.
Выведите одну строку — для каждого типа шифрования «+», если сообщение s могло быть получено в результате его применения, или «-» в противном случае.
frommarsiam 3 6 10 i 2 11 am 1 9 human
++-
В 2030 году Очень Известная Компания выпустила новую клавиатуру. Разработчики решили избавиться от всех ненужных кнопок и оставить только кнопки с первыми \(A\) буквами латинского алфавита. Новая клавиатура пользуется большой популярностью, поэтому Петя решил научиться печатать на ней свое любимое слово (оно не содержит букв, отличных от первых \(A\) букв латинского алфавита).
Петя считает, что он научился, когда на экране можно будет увидеть его любимое слово целиком (то есть найдется последовательность подряд идущих букв, образующих его любимое слово). Например, если Петино любимое слово - "apple", и на экране написано "pineappled", то любимое слово увидеть можно, а если на экране написано "mapplicе", то нельзя. Петя запустил текстовый редактор, и пытается, совершив как можно меньше нажатий на клавиши, добиться появления своего любимого слова.
У Пети есть друг Вася, который хочет, чтобы Петя, напротив, совершил как можно больше нажатий на клавиши - так он лучше научится. В любые моменты (как до того, как Петя начал набирать текст, так и между нажатиями Пети на клавиши) Вася может отпихивать Петю от клавиатуры и печатать на ней что угодно. При этом ни Петя, ни Вася не могут стирать уже напечатанные символы. Суммарно Вася может сделать не более \(K\) нажатий на клавиши (не обязательно подряд), после этого Петя выгонит его из комнаты, и Вася больше никак не будет участвовать в процессе обучения.
Друзья видят, что написано на экране, и знают, сколько клавиш уже нажал каждый из них. Исходя из этого и Петя, и Вася действуют наиболее оптимально.
Напишите программу, которая определит общее количество Петиных нажатий на клавиши, после которого он гарантированно увидит свое любимое слово.
В первой строке входного файла содержатся три целых числа: \(N\), \(A\), \(K\) - длина любимого слова Пети, количество кнопок на клавиатуре и максимальное количество нажатий кнопок Васей соответственно. В следующей строке содержится слово длины \(N\), состоящее из строчных латинских букв - любимое слово Пети. Слово завершает перевод строки.
Выведите одно число - искомое количество нажатий клавиш.
Тесты состоят из четырёх групп.
2 1 2 aa
2
3 4 3 abc
9
3 2 1 aab
4
Для строки S определим ее префикс-функцию: \(\pi [i] = max(k|0 \leq k < i; S[1..k] = S[i - k + 1..i])\) для всех \(1 \leq i \leq N\), где \(N\) — длина строки. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1]. Ваша задача по заданной префикс-функции восстановить строку. В качестве символов строки разрешается использование \(M\) первых строчных букв латинского алфавита.
Входной файл состоит из одного или более набора входных данных. В первой строке каждого набора записаны два целых числа \(N\), \(M\) (\(N \geq 1\), \(1 \leq M \leq 26\)). Во второй строке записана последовательность целых чисел \(\pi [1]\), \(\pi [2]\), ..., \(\pi [N]\). Все числа в последовательности целые неотрицательные, не превосходящие \(10^6\). Сумма значений \(N\) по всем наборам не превосходит \(10^6\), количество наборов входных данных не превосходит \(10^5\).
Выведите в первую строку выходного файла YES если существует искомое слово и NO в противном случае. В случае положительного ответа выведите во вторую строку выходного файла выведите искомое слово. Если решений несколько, выведите любое.
8 3 0 0 1 0 1 2 3 1 1 1 10
YES abacabaa NO