Вам дан массив целых чисел длины 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, 2, ..., N в каком-то фиксированном порядке (каждое из чисел от 1 до N соответствует ровно одной карте). Как и в настоящей игре, Мате не может менять порядок карт.
Домагой указывает Мате на подотрезок последовательности карт, после чего Мате «разворачивает» этот отрезок карт.
При развороте отрезка карт меняются местами первая и последняя карты отрезка, вторая и предпоследняя и так далее. Как и все мы, Домагой — большой любитель неподвижных точек, то есть таких карт, числа на которых совпадают с номером позиции этих карт (считая слева направо со стороны Домагоя). Поэтому Домагой хочет максимизорать число неподвижных точек после поворота какого-то подотрезка.
Помогите Домагою найти такой подотрезок, после разворота которого число неподвижных точек будет максимальным.
В первой строке вводится единственное число N — число кард в руке Мате ( 1 ≤ N ≤ 5·10 5 ). Во второй строке вводятся N различных целых чисел от 1 до N — карты в руке Мате в том порядке, в котором Домагой видит их.
Выведите два числа A и B , числа на картах, являющихся началом и концом отрезка, который надо развернуть, чтобы максимизировать число неподвижных точек.
Программа, верно работающая на тестах, в которых N ≤ 500 , оценивается в 30 баллов. Программа, верно работающая на тестах, в которых N ≤ 5 000 , оценивается в 60 баллов.
4 3 2 1 4
3 1
2 1 2
1 1
7 3 6 5 7 4 1 2
6 1
На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с \(k\) конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.
Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались \(n\) ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер \(1\).
Лена дала коробку другу, который получил номер \(l\), после чего каждый друг Лены, начиная с друга с номером \(l\), брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером \(r\) взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.
Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.
В единственной строке задаются четыре целых числа \(n\), \(l\), \(r\), \(k\) (\(1 \le n, k \le 100\), \(1 \le l, r \le n\)) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку и количество конфет в коробке, соответственно.
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
В первом примере любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету будет четвёртый человек.
Во втором примере сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте.
В третьем примере только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты.
В четвёртом примере Лена ошиблась и такой ситуации быть не могло.
4 1 4 12
2
5 3 4 10
3
10 5 5 1
10
5 4 5 6
-1
Правильные скобочные последовательности определяются следующим образом:
Зная число \(n\), выведите все правильные скобочные последовательности длины \(2n\) в лексикографическом порядке. Символ '(' считается меньше символа ')'.
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 12\)).
Выведите все правильные скобочные последовательности в лексикографическом порядке.