Случилось ужасное! Отважный хорватский охотник попал в его собственную ловушку. В погоне за ценной добычей он помчался вперед и оказался пойман. Чтобы выбраться наружу, он должен решить следующую задачу (а так как умом он не блещет, вам придется ему помочь):
Вам даны 3 целых числа L, D и X. Определите минимальное такое число N , для которого L ≤ N ≤ D и сумма цифр которого равна X . Также определите максимальное M для которого L ≤ M ≤ D и сумма цифр которого равна X . Гарантируется, что такие числа всегда существуют.
В первое строке содержится одно целое число L ( 1 ≤ L ≤ 10000 ). Во второй строке содержится одно целое число D ( 1 ≤ L ≤ D ≤ 10000 ). В третьей строке содержится одно целое число X ( 1 ≤ X ≤ 36 ).
В первой строке выведите одно целое число N из задачи. Во второй строке выведите одно целое число M из задачи.
1 100 4
4 40
100 500 12
129 480
1 10000 1
1 10000
Так же, как и вы, Перо страстно любит задачи. Последняя задача, которая его заинтересовала – определять, является ли слово мультиграммой.
Мультиграмма – это слово, которое состоит из конкатенации двух и более анаграмм. Первая из этих анаграмм называется корнем мультиграммы. Например, слово 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