--->
35 задач
<---
Источники
Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.
В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.
Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).
Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.
Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).
Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.
Выходной файл должен содержать m чисел, по одному на строке.
Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.
Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.
4 abacaba abracadabra aa abra 3 a abra abac
4 2 0
Постройте все циклические сдвиги строки, отсортируйте их и выпишите последний столбец.
Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.
В первой строке выведите два числа - позицию (при нумерации с единицы) исходной строки в отсортированном массиве циклических сдвигов и длину строки. Во второй строке выведите последний столбец таблицы циклических сдвигов.
irtucjb
3 7 jubcirt
«ПермьОлимпБанк» разработал сверхнадежную систему защиты ценных бумаг. В правом верхнем углу любой бумаги должно присутствовать прямоугольное изображение в виде черно-белого рисунка. Для определения подлинности документов была создана библиотека контрольных элементов. Если документ подлинный, то в изображении на документе заданное количество раз присутствует каждый контрольный элемент из библиотеки. В библиотеке нет совпадающих элементов.
Система контроля после сканирования получает изображение в виде цифрового массива N × M, в котором цифра 1 соответствует черному цвету, а цифра 0 — белому. Затем система ищет контрольные элементы в полученном массиве.
Контрольный элемент представляется массивом размером L × L цифр, каждая из которых равна 0 или 1. В библиотеке — K контрольных элементов. Элемент библиотеки должен точно совпадать с какой-либо частью изображения. При сравнении изображения и контрольных элементов повороты не допускаются.
Требуется определить, сколько раз каждый элемент библиотеки встречается в изображении, описанном во входном файле.
В первой строке входных данных записаны через пробел числа N, M, K, L (N ≤ 100 000, M ≤ 1 000, L ≤ 50, K ≤ 20).
Далее следуют по порядку К блоков, соответствующих элементам контрольного образца в библиотеке. Каждый блок состоит из L строк по L цифр (ноль или единица). После каждого блока следует пустая строка.
В последующих N строках записаны по M цифр в каждой, соответствующих изображению.
Выходной файл должны состоять из К строк.
В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 — если элемент не обнаружен).
Номер контрольного элемента из библиотеки в первой строке равен 1, во второй — 2 и т.д. Все числа в строках должны быть разделены пробелом.
Каждый тест оценивается независимо от других.
10 10 2 3 010 111 010 100 011 001 0010010010 0100001111 0000000100 0000100000 0001111000 0000101000 0100000010 0001000110 0011111000 0101000000
1 2 2 1
На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.
Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как ci, то оно будет считаться по формуле ci = ci - 1 + ci - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.
Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.
Казалось бы, после выяснения этого факта отличать волшебные грядки от поддельных стало просто. Но обе корпорации существуют достаточно давно, количество грядок и грибов на них давно превысило все разумные пределы. Вас попросили написать программу, по количеству грибов на грядке сообщающую, является ли эта грядка волшебной.
Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу ai — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.
Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.
Решения, работающие для чисел, не превышающих 263 - 1, будут оцениваться из 30 баллов.
Решения, также работающие для входных данных, не превышающих 15 килобайт, будут оцениваться из еще 30 баллов.
8 1 2 3 4 5 6 7 8
Yes Yes Yes No Yes No No Yes
Участники олимпиады пришли в казанский театр на спектакль, где играют N неизвестных для них актеров. В фойе театра висят портреты всех актеров труппы, которая в полном составе задействована в спектакле. Портреты не подписаны. Зрителям раздали программки, в которых для каждого действия спектакля приводится список фамилий участвующих в нем актеров, но не указаны их роли. Театрал Виталий решил узнать, как выглядит каждый из актеров, упомянутых в программке. Для этого в антракте после каждого действия он выходил в фойе и сопоставлял портреты с увиденными актерами. Требуется написать программу, которая по заданному числу актеров N и списку фамилий актеров, участвующих в каждом из M действий, определяет номер действия, после которого впервые становится возможным установить соответствие между фамилией актера из программки и его портретом.
Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров Ki, участвующих в i–ом действии (1 ≤ Ki ≤ N, K1 + K2 + ... + KM ≤ 100 000), а затем Ki различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.
Выходной файл должен содержать одну строку, состоящую из N записанных через пробел чисел. i-е число этой строки – это номер действия, после которого впервые становится возможным установить соответствие между i–м актером и его портретом. Если к концу спектакля установить соответствие между каким-либо актером и его портретом так и не удалось, то соответствующее число в строке должно быть равно нулю.
В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1. Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
3 3 2 1 2 2 3 2 2 1 2
2 2 1
5 3 3 1 2 3 3 2 1 3 2 1 3
0 3 0 0 0
4 3 1 1 1 3 1 2
1 3 2 3