Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.
У одного медведя есть N строк (обозначим i -ю из них x i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x i и x j ( i < j ) могут принадлежать одной такой последовательности, если x i является и префиксом, и суффиксом x j .
Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.
В первой строке содержится одно целое число N – количество строк, которые есть у медведя. В последующих N строках содержатся сами эти строки. Входной файл содержит не более двух миллионов символов.
Выведите одно число – ответ на вопрос любопытного генерала Хендрика.
В первом примере наибольшая последовательность A -> AA -> AAA В третьем примере наибольшая последовательность A -> A -> A или B -> B -> B
5 A B AA BBB AAA
3
5 A ABA BBB ABABA AAAAAB
3
6 A B A B A B
3
Юный Мирко решил купить куклу вуду. Учитывая что он крайне заинтересован в том, ктобы купить ее как можно дешевле, он начал отслеживать цены на кукол вуду каждый день. Его список состоит из цен на куклы в последние N дней, где a i обозначает цену куклы i дней назад.
Мирко думает, что нашел связь между средней ценой кукол в течении нескольких последовательных дней и ценой куклы в следующий день. Он хочет проверить свою догадку и задался вопросом: "Для данного числа P , сколько существует наборов последовательных дней в течении последних N дней, для которых средняя цена куклы в эти дни составляет не менее P ".
Два набора последовательных дней считаются различными, если у них отличается первый или последний день.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ \(10^6\) ), количество дней в списке Мирко. Вторая строка содержит N целых чисел a i ( 0 ≤ a i ≤\(10^9\) ) - цены кукол в соответствующие дни. Третья строка содержит одно целое число P ( 0 ≤ P ≤\(10^9\) ).
Выведите одно целое число - ответ на вопрос Мирко для данного P .
3 1 2 3 3
1
3 1 3 2 2
5
3 1 3 2 3
1
В распоряжении агрономического комбината «Олег и ко» находится n полей, пронумерованных от 1 до n . Для каждого поля определена его урожайность a i ≤ 10 9 — сколько килограмм винограда можно собрать с этого поля за год.
В связи с трудной экономической ситуацией руководству фирмы приходится принимать решительные (хоть и не совсем честные) меры по повышению стоимости акций предприятия. Руководство знает, что стоимость акций равна среднему арифметическому урожайностей полей, принадлежащих комбинату. Но эта величина может быть очень маленькой, поэтому руководство приняло решение сообщать при регистрации не обо всех полях, а лишь о каком-то множестве полей с последовательными индексами. Кроме того, некоторые поля не отвечают высоким стандартам производства винограда, поэтому регистрировать их нельзя (иначе фирму могут закрыть). Однако все знают, что у комбината более одного поля, поэтому регистрация одного поля будет выглядеть подозрительно, и, поэтому, директор всегда будет регистрировать не менее двух полей.
Вам необходимо помочь руководству фирмы и ответить на q запросов. Запросы могут быть одного из двух видов:
1 l r x — урожайность полей с номерами от l до r увеличиласть на x ( 1 ≤ x ≤ 10 9 ).
2 l r — предположим, разрешено регистрировать поля с номерами от l до r ( 1 ≤ l < r ≤ n ). Какой максимальной прибыли может добиться директор при правильном выборе полей, которые он будет регистрировать?
В первой строке входного файла задано 2 целых числа n и q — число полей у комбината и число запросов соответсвтенно.
Во второй строке задано n целых чисел a i ( 1 ≤ a i ≤ 10 9 ) через пробел — изначальные урожайности полей.
В следующих q строках заданы запросы в формате, описанном выше.
Для каждого запроса второго типа выведите вещественное число в отдельной строке — ответ на задачу. Ваш ответ будет считаться корректным если абсолютная или относительная погрешность не превосходит 10 - 4 .
n , q ≤ 100 — 15 баллов.
n , q ≤ 1000 — 50 баллов.
n , q ≤ 5·10 5 — 100 баллов.
3 3 2 1 2 2 1 3 1 2 2 4 2 1 3
1.66667 3.50000
Вам дан массив целых чисел длины 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
Пусть дан строчный латинский символ c . Тогда операция shift ( c ) превращает c в следующий по порядку символ в алфавите. Например, shift (a) = b, shift (e) = f, shift (z) = a.
Дана строка S , состоящая из N строчных латинских символов (индексация с 0). Необходимо обработать Q запросов 2 типов:
"1 i j t": ко всем элементам строки с индексами в отрезке [i:j] применить t раз операцию shift .
"2 i j": найдите количество непустых подмножеств символов строки { c 1 , c 2 , ... , c k }, где i ≤ index c 1 < index c 2 < ... < index c k ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 9 + 7 .
Два подмножества символов строки называются различными, если множества индексов их элементов различаются.
Строка называется палиндромом, если читается слева направо также, как справа налево.
Первая строка содержит два целых числа N и Q ( 1 ≤ N , Q ≤ 10 5 ) - длину строки и количество запросов соответственно. Вторая строка содержит одну строку S длины N , состоящую из строчных латинских символов. Каждая из последующих Q строк содержит запрос в формате, описанном в условии.
Для каждого запроса второго типа выведите одно целое число - ответ на данный запрос.
Решения, работающие при N ≤ 500 и Q ≤ 500 , будут оцениваться в 20 баллов.
Решения, работающие при условии, что все запросы являются запросами второго типа, оцениваются еще в 30 баллов.
3 5 aba 2 0 2 2 0 0 2 1 2 1 0 1 1 2 0 2
5 1 2 3
5 7 acdec 2 0 3 1 3 4 36 1 2 3 81 1 1 4 11 2 3 3 2 2 3 2 1 2
4 1 2 2