Так же, как и вы, Перо страстно любит задачи. Последняя задача, которая его заинтересовала – определять, является ли слово мультиграммой.
Мультиграмма – это слово, которое состоит из конкатенации двух и более анаграмм. Первая из этих анаграмм называется корнем мультиграммы. Например, слово bbabab – мультиграмма с корнем bba, потому что она состоит из анаграмм bba и bab.
Помогите Перо определять, является ли данное ему слово мультиграммой, и если да, определить корень. Если возможных ответов несколько, выведите кратчайший.
Единственная строка содержит слово, состоящее не более, чем из 10 5 строчных букв латинского алфавита.
Если данное слово – мультиграмма, выведите кратчайший из её корней. Иначе выведите -1.
Решения, работающие когда длина строки не превосходит 500, будут оцениваться в 20 баллов.
Решения, работающие когда длина строки не превосходит 5000, будут оцениваться в 40 баллов.
aaaa
a
ab
-1
bbabab
bba
Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.
Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.
В первой строке содержатся два целых числа N и K ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 50 ). Во второй строке содержатся N целых чисел a i ( 0 ≤ a i ≤ 10 9 ) - числа на клавишах пианино.
В единственной строке выведите одно целое число - ответ на вопрос Перики по модулю 1000000007.
Решения, работающие при 1 ≤ N ≤ 1000 , будут оцениваться в 40 баллов.
5 3 2 4 2 3 4
39
5 1 1 0 1 1 1
4
5 2 3 3 4 0 0
31
У маленького Матежа возникла проблема с решением следующей задачи.
У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.
Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.
В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.
Выведите Q строк: в каждой ответ для соответствующего шаблона.
40 баллов: 1 ≤ N , Q ≤ 1000
3 3 aaa abc aba a*a aaa* *aaa
2 1 1
5 3 eedecc ebdecb eaba ebcddc eb e* *dca e*c
5 0 2
Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.
Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .
Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .
Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s ) = ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.
Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .
В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).
Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).
Гарантируется, что во всех тестах K ≤ 2 N - 1 .
Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .
Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.
2 3 1 5 1 2
1 1 3 2 2 1
3 4 2 3 1 3 1
1 1 1 1 0 2 2 2
5 6 23 1000 1 2 4 2 3
1 1 25 2 25 2 577 3 274 4 578 3
Ночью Мирко приснилась гистограмма из N столбиков. Каждый из них имел ширину в 1 метр, а высоты столбиков в метрах равны h 1 , h 2 , ... , h N .
Вместимостью гистограммы называется максимальное количество воды (в квадратных метрах) которое она может удержать так, что конфигурация воды "стабильная", иными словами, вода в ней не перемещается под воздействием сил гравитации.
Формально, пусть количество воды над столбиками равно v 1 , v 2 , ... , v N соответственно. Тогда конфигурация воды стабильна, если выполняются следующие условия:
1. h i + v i ≤ h i - 1 + v i - 1 для каждого i ≥ 2 , такого что v i > 0 .
2. h i + v i ≤ h i + 1 + v i + 1 для каждого i ≤ N - 1 , такого что v i > 0 .
3. v 1 = 0 и v N = 0 .
Проснувшись, Мирко захотел нарисовать такую гистограмму, чтобы высоты ее столбиков были перестановкой множества {1, 2, ... , N} и ее вместимость была в точности равна его счастливому числу X . Помогите Мирко и найдите такую гистограмму.
Единственная строка содержит два целых числа N и X ( 1 ≤ N ≤ 1000000 , 1 ≤ X ≤ 10 15 ).
Если гистограмма вместимости X не существует, выведите -1.
Иначе, выведите числа h 1 , h 2 , ... , h N (являющиеся перестановкой множества {1, 2, ... , N}), удовлетворяющие условию задачи. Если существует несколько решений, выведите любое.
25 баллов — (1 ≤ n ≤ 10) .
25 баллов — (0 ≤ x ≤ n - 2 ) .
50 баллов — полные ограничения.
3 1
3 1 2
4 1
4 3 1 2
8 17
6 2 3 1 8 4 5 7