ICPC 2022-2023 NERC (NEERC), квалификационный этап Чемпионата Юга и Поволжья России
A. Как можно быстрее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в новую компьютерную игру. Действие в ней происходит на горизонтальной оси $$$oX$$$.

На очередном уровне герой игры находится в точке $$$0$$$ и должен попасть в точку $$$n$$$. Для этого он может выполнять два типа перемещений:

  • переместиться в соседнюю слева или справа точку, на это действие тратится $$$a$$$ секунд (то есть из точки $$$x$$$ герой может переместиться в точку $$$x - 1$$$ или $$$x + 1$$$ за $$$a$$$ секунд);
  • прыгнуть на расстояние $$$d$$$ влево или вправо, на это действие тратится $$$b$$$ секунд (то есть из точки $$$x$$$ герой может прыгнуть в точку $$$x - d$$$ или $$$x + d$$$ за $$$b$$$ секунд).

Обратите внимание, что в результате перемещений герой игры может оказаться левее точки $$$0$$$ или правее точки $$$n$$$, это допустимо, ведь игровая прямая бесконечна.

Перед вами стоит задача определить минимальное время, за которое герой игры может добраться до точки $$$n$$$, изначально находясь в точке $$$0$$$.

Входные данные

В первой строке следуют четыре целых числа $$$n$$$, $$$a$$$, $$$b$$$ и $$$d$$$ ($$$1 \le n \le 1\,000$$$, $$$1 \le a \le 1\,000$$$, $$$1 \le b \le 1\,000$$$, $$$1 \le d \le n$$$) — точка, в которую должен попасть герой игры, время, которое необходимо для перемещения в соседнюю точку, время, которое необходимо для совершения прыжка, а также расстояние, на которое можно переместиться во время прыжка.

Выходные данные

Выведите одно целое число — минимальное время, за которое герой игры может добраться до точки $$$n$$$, изначально находясь в точке $$$0$$$.

Примеры
Входные данные
9 7 6 5
Выходные данные
19
Входные данные
20 5 10 15
Выходные данные
35
Входные данные
4 3 5 2
Выходные данные
10
Примечание

В первом примере герой игры может, например, сначала переместиться влево в соседнюю точку за $$$7$$$ секунд. После этого он окажется в точке $$$-1$$$. Затем он может два раза прыгнуть вправо, оказавшись сначала в точке $$$4$$$, а затем в точке $$$9$$$. На прыжки он потратит $$$12$$$ секунд. Таким образом, весь путь он преодолеет за $$$7 + 12 = 19$$$ секунд.

Во втором примере герой игры может, например, сначала прыгнуть один раз вправо. После этого он окажется в точке $$$15$$$, потратив на это $$$10$$$ секунд. Затем ему нужно $$$5$$$ раз переместиться вправо в соседнюю клетку. После этого он окажется в точке $$$20$$$. Суммарное затраченное время будет равно $$$10 + 5 \cdot 5 = 35$$$ секунд.

В третьем примере герою игры нужно два раза прыгнуть вправо. После этого он окажется в точке $$$4$$$ за $$$10$$$ секунд.

B. Стоимость перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$. Вы должны построить перестановку размера $$$n$$$.

Перестановка — это массив, в котором каждое число от $$$1$$$ до $$$s$$$ (где $$$s$$$ — размер перестановки) встречается ровно один раз. Например, $$$[2, 1, 4, 3]$$$ — перестановка размера $$$4$$$; $$$[1, 2, 4, 5, 3]$$$ — перестановка размера $$$5$$$; $$$[1, 4, 3]$$$ — не перестановка (число $$$2$$$ отсутствует), $$$[2, 1, 3, 1]$$$ — не перестановка (число $$$1$$$ встречается дважды).

Подотрезок перестановки — это непрерывная подпоследовательность перестановки. Например, у перестановки $$$[2, 1, 4, 3]$$$ $$$10$$$ подотрезков: $$$[2]$$$, $$$[2, 1]$$$, $$$[2, 1, 4]$$$, $$$[2, 1, 4, 3]$$$, $$$[1]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$, $$$[4]$$$, $$$[4, 3]$$$ и $$$[3]$$$.

Стоимость перестановки — это количество ее подотрезков, которые также являются перестановками. Например, стоимость перестановки $$$[2, 1, 4, 3]$$$ равна $$$3$$$, так как подотрезки $$$[2, 1]$$$, $$$[1]$$$ и $$$[2, 1, 4, 3]$$$ являются перестановками.

Вы должны вывести перестановку размера $$$n$$$ с минимально возможной стоимостью среди всех перестановок размера $$$n$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 48$$$) — количество наборов входных данных.

Затем следуют $$$t$$$ строк. В $$$i$$$-й из них задано одно целое число $$$n$$$ ($$$3 \le n \le 50$$$), обозначающее $$$i$$$-й набор входных данных.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — перестановку размера $$$n$$$ с минимально возможной стоимостью. Если существует несколько таких перестановок, выведите любую из них.

Пример
Входные данные
2
5
6
Выходные данные
1 4 3 5 2
4 1 6 2 5 3
Примечание

В первом примере перестановка $$$[1, 4, 3, 5, 2]$$$ — один из возможных ответов; ее стоимость равна $$$2$$$.

Во втором примере перестановка $$$[4, 1, 6, 2, 5, 3]$$$ — один из возможных ответов; ее стоимость равна $$$2$$$.

C. Перевороты и удаления
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из символов a и/или b.

Монокарп выполнит со своей строкой $$$k$$$ ($$$2k \lt n$$$) раз подряд следующую операцию:

  1. если первый и последний символы строки разные, то Монокарп переворачивает свою строку (то есть первый символ строки станет последним, второй символ строки станет предпоследним и так далее);
  2. вне зависимости от первого шага Монокарп удаляет первый и последний символы своей строки.

Определите, как будет выглядеть строка Монокарпа после проведения им $$$k$$$ операций. Обратите внимание, что ограничения на $$$k$$$ таковы, что в строке Монокарпа после всех операций гарантированно будет хотя бы один символ.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 200\,000$$$, $$$1 \le k$$$, $$$2k \lt n$$$) — длина строки Монокарпа и количество операций.

Во второй строке следует строка Монокарпа $$$s$$$ длины $$$n$$$, состоящая из символов a и/или b.

Выходные данные

Выведите строку Монокарпа после применения к ней $$$k$$$ описанных в условии операций.

Примеры
Входные данные
6 2
ababbb
Выходные данные
ba
Входные данные
13 4
bababbaaababb
Выходные данные
aaabb
Входные данные
8 2
abaaabab
Выходные данные
aaab
Входные данные
7 1
ababbab
Выходные данные
abbab
Входные данные
3 1
bba
Выходные данные
b
Входные данные
6 1
aababa
Выходные данные
abab
Примечание

В первом примере в ходе первой операции строка будет перевернута и станет равна bbbaba, а затем будут удалены первый и последний символы и строка станет равна bbab. В ходе второй операции строка перевернута не будет, а после удаления первого и последнего символов строка станет равна ba.

D. Пароль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп забыл пароль от своего телефона. Пароль состоит ровно из $$$6$$$ цифр от $$$0$$$ до $$$9$$$ (обратите внимание, что пароль может начинаться с цифры $$$0$$$).

Монокарп помнит, что в его пароле были ровно две различные цифры, причем каждая из этих цифр встречалась в пароле ровно по три раза. Также Монокарп помнит, какие цифры точно не могли быть в его пароле.

Посчитайте количество последовательностей из $$$6$$$ цифр, которые могли бы быть паролем Монокарпа (то есть которые подходят под все описанные условия).

Входные данные

В первой строке следует целое число $$$n$$$ ($$$1 \le n \le 8$$$) — количество цифр, которых точно нет в пароле Монокарпа.

Во второе строке следуют $$$n$$$ целых различных чисел $$$a_1, a_2, \dots a_n$$$ ($$$0 \le a_i \le 9$$$) — цифры, которых точно нет в пароле Монокарпа. Обратите внимание, что числа $$$a_1, a_2, \dots, a_n$$$ заданы в порядке возрастания.

Выходные данные

Выведите одно целое число — количество последовательностей из $$$6$$$ цифр, которые подходят под все описанные условия.

Примеры
Входные данные
8
0 1 2 4 5 6 8 9
Выходные данные
20
Входные данные
1
8
Выходные данные
720

E. d-сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$. Он может выполнять со своей последовательностью следующую операцию неограниченное количество раз:

  • выбрать две позиции $$$i$$$ и $$$j$$$ ($$$i \lt j$$$), находящиеся на расстоянии $$$d$$$ друг от друга (то есть $$$j - i = d$$$), и поменять местами значения в этих позициях, то есть поменять местами $$$a_i$$$ и $$$a_j$$$.

Перед вами стоит задача определить, может ли Монокарп с помощью некоторого (возможно нулевого) количества описанных операций сделать свою последовательность неубывающей (то есть, чтобы для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$ было верно, что $$$a_i \le a_{i + 1}$$$).

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le n - 1$$$) — количество элементов в последовательности и расстояние, на котором должны находится элементы последовательности для обмена в ходе операций.

Во второй строке следуют $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — описание последовательности Монокарпа.

Выходные данные

Если Монокарп может сделать свою последовательность неубывающей с помощью описанных операций, выведите «YES» (без кавычек). В противном случае, выведите «NO».

Примеры
Входные данные
4 2
6 7 1 4
Выходные данные
YES
Входные данные
5 3
5 6 6 10 10
Выходные данные
YES
Входные данные
8 3
4 5 3 1 3 4 2 4
Выходные данные
NO
Примечание

В первом примере можно с помощью одной операции поменять первый и третий элементы (после этого последовательность станет равна $$$[1, 7, 6, 4]$$$), а затем с помощью еще одной операции поменять второй и четвертый элементы (после этого последовательность станет равна $$$[1, 4, 6, 7]$$$). Таким образом, последовательность станет отсортированной по неубыванию.

Во втором примере последовательность изначально является неубывающей, поэтому никаких операций применять не нужно.

F. Журналы Монокарпа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп очень долго коллекционировал разные журналы и теперь решил их продать. Для этого он выставил в ряд $$$n$$$ коробок с журналами, причем в $$$i$$$-й коробке находится $$$a_i$$$ журналов. Некоторые из коробок он накрыл крышками.

Внезапно пошел дождь, и Монокарпу нужно спасти от дождя как можно большее количество журналов. Для этого он может сделать следующее: если коробка $$$i$$$ изначально была накрыта крышкой, он может либо переместить крышку с коробки $$$i$$$ на коробку $$$(i-1)$$$ (если она есть), либо оставить крышку на коробке $$$i$$$. Считайте, что все перемещения крышек Монокарп выполнит мгновенно, и каждая крышка будет перемещена не более одного раза. Журналы, которые после перемещения будут находиться в коробках с крышками, будут спасены от дождя; все остальные журналы намокнут.

Перед вами стоит задача определить максимальное количество журналов, которые Монокарп может спасти от дождя.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество коробок с журналами.

Во второй строке следует строка, состоящая из $$$n$$$ символов 0 и/или 1. Если $$$i$$$-й символ строки равен 1, то изначально $$$i$$$-я коробка накрыта крышкой. Если $$$i$$$-й символ строки равен 0, то изначально $$$i$$$-я коробка не накрыта крышкой.

В третьей строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), где $$$a_i$$$ равно количеству журналов в $$$i$$$-й коробке.

Выходные данные

Выведите максимальное количество журналов, которые Монокарп может спасти от дождя.

Примеры
Входные данные
5
01110
10 5 8 9 6
Выходные данные
27
Входные данные
6
011011
20 10 9 30 20 19
Выходные данные
80
Входные данные
4
0000
100 100 100 100
Выходные данные
0
Входные данные
4
0111
5 4 5 1
Выходные данные
14
Примечание

В первом примере нужно переместить крышку со второй коробки влево на первую коробку. Тогда коробки $$$1$$$, $$$3$$$ и $$$4$$$ будут накрыты крышками, и $$$10 + 8 + 9 = 27$$$ журналов будут спасены от дождя.

Во втором примере нужно переместить крышку со второй коробки на первую коробку, крышку с третьей коробки на вторую коробку, крышку с пятой коробки на четвертую коробку, крышку с шестой коробки на пятую коробку. Тогда коробки $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$ будут накрыты крышками, и $$$20 + 10 + 30 + 20 = 80$$$ журналов будут спасены от дождя.

В третьем примере нет ни одной крышки, поэтому ни один из журналов нельзя спасти от дождя.

G. Итоговая оценка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп занимается фигурным катанием и участвует в большом соревновании. За его выступлением следили $$$n$$$ судей. Каждый судья поставил оценку за выступление Монокарпа — целое число от $$$1$$$ до $$$10^{9}$$$ (чем выше оценка, тем лучше выступление).

По новым правилам фигурного катания, в соответствии со списком $$$n$$$ оценок судей, итоговая оценка выступления — это ровно одно целое число, получаемое с помощью следующих операций:

  • берется минимальная оценка $$$x$$$ и максимальная оценка $$$y$$$. Обе эти оценки удаляются из списка оценок (если $$$x$$$ встречается в списке несколько раз, удаляется только одно вхождение; то же самое верно для $$$y$$$), а вместо них в список оценок добавляется оценка, равная $$$\frac{x + y}{2}$$$, округленная вниз к ближайшему целому числу.

После применения $$$n - 1$$$ описанных операций в списке оценок останется ровно одна, которая и будет итоговой оценкой выступления.

Перед вами стоит задача определить итоговую оценку выступления Монокарпа.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество изначальных оценок за выступление Монокарпа.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — изначальные оценки, полученные Монокарпом от судей.

Выходные данные

Выведите одно целое число — итоговую оценку выступления Монокарпа, которую он получит в соответствии с описанным в условии алгоритмом.

Примеры
Входные данные
5
3 6 1 9 1
Выходные данные
3
Входные данные
8
12 12 40 30 20 24 21 13
Выходные данные
20
Входные данные
3
100 100 100
Выходные данные
100
Примечание

Отсортированный список всех оценок в первом примере равен $$$[1, 1, 3, 6, 9]$$$.

Во время первой операции $$$x = 1$$$, $$$y = 9$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{1 + 9}{2} = 5$$$. Поэтому после операции список оценок будет равен $$$[1, 3, 5, 6]$$$.

Во время второй операции $$$x = 1$$$, $$$y = 6$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{1 + 6}{2} = 3$$$ (по условию округляем вниз). Поэтому после операции список оценок будет равен $$$[3, 3, 5]$$$.

Во время третьей операции $$$x = 3$$$, $$$y = 5$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{3 + 5}{2} = 4$$$. Поэтому после операции список оценок будет равен $$$[3, 4]$$$.

Во время четвертой операции $$$x = 3$$$, $$$y = 4$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{3 + 4}{2} = 3$$$ (по условию округляем вниз). Поэтому после операции список оценок будет равен $$$[3]$$$.

Таким образом, в первом итоговая оценка Монокарпа за выступление равна $$$3$$$.

H. Подготовка к докладу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп является студентом и учится в университете в группе вместе с другими $$$n$$$ студентами.

По предмету языкознания преподаватель задал подготовить доклад по книге, состоящей из $$$m$$$ страниц. Все страницы книги пронумерованы по очереди, начиная со страницы $$$1$$$. Для подготовки к докладу каждую страницу книги должен прочитать хотя бы один из студентов в группе.

За день до презентации доклада оказалось, что $$$i$$$-й из $$$n$$$ студентов (без учета Монокарпа) прочитал подряд все страницы книги, начиная со страницы $$$a_i$$$ до страницы $$$b_i$$$, включительно ($$$a_i \le b_i$$$).

Перед вами стоит задача определить минимальное количество подряд идущих страниц, которые должен прочитать Монокарп, чтобы каждая страница книги была прочитана одним из студентов группы. Монокарп будет читать страницы подряд, потому что он считает, что таким образом лучше подготовится к презентации доклада.

Если оказалось так, что каждая страница книги прочитана хотя бы одним студентом до того, как Монокарп начнет чтение, он читать ничего не будет.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 10^{9}$$$) — количество студентов в группе без учета Монокарпа, а также количество страниц в книге.

В $$$i$$$-й из следующих $$$n$$$ строк следуют по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le b_i \le m$$$) — информация о начальной и конечной страницах, прочитанных $$$i$$$-м студентом. То есть $$$i$$$-й студент прочитал подряд все страницы книги, начиная со страницы $$$a_i$$$ и заканчивая страницей $$$b_i$$$.

Выходные данные

Выведите одно целое число — минимальное количество подряд идущих страниц, которые нужно прочитать Монокарпу, чтобы каждая из страниц книги была прочитана хотя бы одним студентом группы. Если читать Монокарпу ничего не нужно, выведите $$$0$$$.

Примеры
Входные данные
2 6
1 2
5 6
Выходные данные
2
Входные данные
3 10
2 7
5 8
9 9
Выходные данные
10
Входные данные
2 15
1 13
4 15
Выходные данные
0
Примечание

В первом примере Монокарпу нужно прочитать третью и четвертую страницы книги. Тогда каждая из страниц книги будет прочитана хотя бы одним студентом группы.

Во втором примере не прочитана первая и последняя страницы книги. Поэтому Монокарпу нужно прочитать все $$$10$$$ страниц книги, так как он решил читать страницы книги подряд.

В третьем примере Монокарпу не нужно ничего читать, так как каждая страница книги уже прочитана хотя бы одним из студентов.

I. Фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп живет на улице, которая расположена вдоль оси $$$oX$$$. Улица начинается в точке $$$0$$$ и заканчивается в точке $$$f$$$. Также на улице есть $$$n$$$ столбов, расположенных в различных точках $$$a_1, a_2, \dots, a_n$$$.

На каждый столб можно повесить фонарь, который будет освещать определенный участок улицы. Если столб, на который повесили фонарь, находится в точке $$$x$$$, а мощность фонаря равна $$$y$$$, то будет освещен участок улицы от точки $$$x - y$$$ до точки $$$x + y$$$, включительно.

У Монокарпа есть $$$k$$$ фонарей, причем каждый фонарь можно настроить на любую мощность. Обратите внимание, что мощность освещения фонаря должна быть целым положительным числом.

С помощью своих фонарей Монокарп хочет осветить всю улицу, то есть каждая точка от $$$0$$$ до $$$f$$$ должна быть освещена. Обратите внимание, что должны быть освещены все точки от $$$0$$$ до $$$f$$$, в том числе и нецелочисленные.

Для этого он выберет $$$k$$$ столбов, на которые повесит фонари (на каждый столб ровно по одному фонарю), а также настроит все фонари на одинаковую мощность $$$d$$$.

Монокарп хочет сэкономить на потреблении электроэнергии (ведь чем мощнее светит фонарь, тем больше электроэнергии ему необходимо), поэтому перед вами стоит задача определить минимальное значение мощности каждого фонаря, которого будет достаточно, чтобы с помощью $$$k$$$ фонарей были освещены все точки улицы от $$$0$$$ до $$$f$$$.

Входные данные

В первой строке следуют три целых числа $$$n$$$, $$$k$$$ и $$$f$$$ ($$$1 \le k \le n \le 200\,000$$$, $$$1 \le f \le 10^{9}$$$) — количество столбов, на которые можно повесить фонари, количество фонарей и самая правая точка улицы.

Во второй строке следует последовательность различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le f$$$) — точки, в которых расположены столбы.

Выходные данные

Выведите минимальное значение мощности каждого фонаря (каждый из $$$k$$$ фонарей Монокарп настроит на одинаковую мощность), которого будет достаточно, чтобы с помощью $$$k$$$ фонарей были освещены все точки улицы от $$$0$$$ до $$$f$$$ (в том числе и нецелочисленные).

Примеры
Входные данные
2 1 12
6 4
Выходные данные
6
Входные данные
4 2 20
3 6 13 19
Выходные данные
7
Входные данные
2 2 1
0 1
Выходные данные
1
Входные данные
2 1 1
0 1
Выходные данные
1
Входные данные
10 4 100
34 52 12 35 89 60 77 43 23 11
Выходные данные
15
Примечание

В первом примере нужно повесить фонарь на столб в точке $$$6$$$, а его мощность должна быть равна $$$6$$$. Тогда все точки улицы от $$$0$$$ до $$$12$$$ будут освещены.

Во втором примере можно повесить фонари на столбы в точках $$$3$$$ и $$$13$$$, а мощность каждого фонаря установить равной $$$7$$$. Тогда все точки улицы от $$$0$$$ до $$$20$$$ будут освещены. Обратите внимание, что фонарь на столбе в точке $$$3$$$ будет освещать участок $$$[-4, 10]$$$, и это допустимо.

В третьем примере можно повесить фонари на оба столба, а мощность каждого должна быть равна $$$1$$$, так как должны быть освещены все точки улицы, в том числе и нецелочисленные, а мощность каждого фонаря должна быть целым числом.

В четвертом примере можно повесить фонарь на любой из столбов, установив мощность освещения равную $$$1$$$. Тогда все точки улицы от $$$0$$$ до $$$1$$$ будут освещены.

J. Задача со случайными тестами
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ из $$$n$$$ символов. Каждый символ $$$s$$$ — либо 0, либо 1.

Подстрока строки $$$s$$$ — это непрерывная подпоследовательность ее символов.

Вы должны выбрать две подстроки $$$s$$$ (возможно, пересекающиеся, возможно, одну и ту же два раза, возможно, непересекающиеся — две любые подстроки). После того как вы выбрали подстроки, вы считаете их стоимость следующим образом:

  • пусть $$$s_1$$$ — первая подстрока, $$$s_2$$$ — вторая подстрока, а $$$f(s_i)$$$ — целое число, для которого $$$s_i$$$ является записью в двоичной системе счисления (напримре, если $$$s_i$$$ — это 11010, то $$$f(s_i) = 26$$$);
  • стоимость пары подстрок — это побитовое ИЛИ чисел $$$f(s_1)$$$ и $$$f(s_2)$$$.

Посчитайте максимальную стоимость, которую вы можете получить, и выведите ее в двоичной системе счисления без ведущих нулей.

Входные данные

В первой строке задано число $$$n$$$ — количество символов в $$$s$$$.

Во второй строке задана $$$s$$$, состоящая из ровно $$$n$$$ символов 0 и/или 1.

Все тесты в этой задаче, кроме примеров из условия, сгенерированы случайным образом: каждый символ $$$s$$$ выбирается независимо от остальных, и для каждого символа вероятность быть 1 равна $$$\frac{1}{2}$$$.

В этой задаче ровно $$$40$$$ тестов. Тесты с $$$1$$$ по $$$3$$$ — примеры из условия; тесты с $$$4$$$ по $$$40$$$ сгенерированы случайным образом. В тестах с $$$4$$$ по $$$10$$$ $$$n = 5$$$; в тестах с $$$11$$$ по $$$20$$$ $$$n = 1000$$$; в тестах с $$$21$$$ по $$$40$$$ $$$n = 10^6$$$.

Выходные данные

Выведите максимальную стоимость, которую можно получить, в двоичной системе счисления без ведущих нулей.

Примеры
Входные данные
5
11010
Выходные данные
11111
Входные данные
7
1110010
Выходные данные
1111110
Входные данные
4
0000
Выходные данные
0
Примечание

В первом примере можно выбрать подстроки 11010 и 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, их побитовое ИЛИ равно $$$31$$$, а двоичное представление $$$31$$$ — это 11111.

Во втором примере можно выбрать подстроки 1110010 и 11100.

K. FTL
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру. В этой игре он управляет космическим кораблем. Его цель — уничтожить космический корабль противника.

На корабле Монокарпа установлены два лазера. Оба лазера $$$1$$$ и $$$2$$$ характеризуются двумя значениями:

  • $$$p_i$$$ — мощность лазера;
  • $$$t_i$$$ — время перезарядки лазера.

Когда лазер полностью заряжен, Монокарп может либо выстрелить из него, либо дождаться полной зарядки другого лазера и выстрелить из них обоих одновременно.

У корабля противника $$$h$$$ прочности и $$$s$$$ силы щита. Когда Монокарп стреляет по кораблю противника, тот получает $$$(P - s)$$$ урона (т. е. $$$(P - s)$$$ вычитается из его прочности), где $$$P$$$ — это суммарная мощность лазеров, из которых выстрелил Монокарп (т. е. $$$p_i$$$, если он стрелял только из лазера $$$i$$$, и $$$p_1 + p_2$$$, если он стрелял из обоих одновременно). Корабль противника считается уничтоженным, когда его прочность становится меньше или равна $$$0$$$.

Изначально оба лазера разряжены.

За какое наименьшее время Монокарп может уничтожить корабль противника?

Входные данные

В первой строке записаны два целых числа $$$p_1$$$ и $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — мощность и время перезарядки первого лазера.

Во второй строке записаны два целых числа $$$p_2$$$ и $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — мощность и время перезарядки второго лазера.

В третьей строке записаны два целых числа $$$h$$$ и $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s \lt \min(p_1, p_2)$$$) — прочность и сила щита корабля противника. Обратите внимание, что последнее ограничение подразумевает, что Монокарп всегда может уничтожить корабль противника.

Выходные данные

Выведите одно целое число — наименьшее время, за которое Монокарп может уничтожить корабль противника.

Примеры
Входные данные
5 10
4 9
16 1
Выходные данные
20
Входные данные
10 1
5000 100000
25 9
Выходные данные
25
Примечание

В первом примере Монокарп ждет зарядки обоих лазеров, затем стреляет из обоих в $$$10$$$, они наносят $$$(5 + 4 - 1) = 8$$$ единиц урона. Затем он снова ждет и стреляет из обоих лазеров в $$$20$$$, нанося еще $$$8$$$ единиц урона.

Во втором примере Монокарп не ждет зарядки второго лазера. Он просто стреляет из первого $$$25$$$ раз, нанося $$$(10 - 9) = 1$$$ единицу урона каждый раз.

L. Пересечение и объединение
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ отрезков на координатной прямой. $$$i$$$-й отрезок — это $$$[l_i, r_i]$$$. Обозначим множество всех целочисленных точек, принадлежащих $$$i$$$-му отрезку, за $$$S_i$$$.

Пусть $$$A \cup B$$$ — объединение множеств $$$A$$$ и $$$B$$$, $$$A \cap B$$$ — пересечение множеств $$$A$$$ и $$$B$$$, а $$$A \oplus B$$$ — симметрическая разность $$$A$$$ и $$$B$$$ (множество, в которые входят все элементы $$$A$$$ и все элементы $$$B$$$, кроме тех, которые встречаются в обоих множествах).

Пусть $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ — массив, где каждый элемент — либо $$$\cup$$$, либо $$$\oplus$$$, либо $$$\cap$$$. По всем $$$3^{n-1}$$$ способам выбрать этот массив посчитайте сумму следующих значений:

$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$

В этом выражении $$$|S|$$$ означает размер множества $$$S$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

Затем следуют $$$n$$$ строк. В $$$i$$$-й из них заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$).

Выходные данные

Выведите одно целое число — сумму $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ по всем возможным способам выбрать $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
4
3 5
4 8
2 2
1 9
Выходные данные
162
Входные данные
4
1 9
3 5
4 8
2 2
Выходные данные
102

M. Антифибоначчиевый разрез
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на нестандартное ограничение памяти.

Введем последовательность строк Фибоначчи следующим образом: $$$f_0$$$ — строка 0, $$$f_1$$$ — строка 1, $$$f_i$$$ строится по формуле $$$f_{i-1} + f_{i-2}$$$ при $$$i \gt 1$$$ ($$$+$$$ обозначает конкатенацию строк). Например, $$$f_2$$$ — 10, $$$f_3$$$ — 101, $$$f_4$$$ — 10110.

Для строки $$$s$$$ обозначим за $$$g(s)$$$ количество способов разрезать эту строку на строки, из которых ни одна не является строкой Фибоначчи. Например, если $$$s$$$ — 10110101, $$$g(s) = 3$$$, так как существуют три способа разрезать строку:

  • 101101 $$$+$$$ 01;
  • 1011 $$$+$$$ 0101;
  • 1011 $$$+$$$ 01 $$$+$$$ 01.

Вам дана последовательность строк $$$s_1, s_2, \dots, s_n$$$. Посчитайте $$$g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$$$. Так как эти значения могут быть очень большими, выведите их по модулю $$$998244353$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$).

Затем следуют $$$n$$$ строк. В $$$i$$$-й из них задана $$$s_i$$$ ($$$1 \le |s_i| \le 10^3$$$), состоящая из символов 0 и/или 1.

Выходные данные

Выведите $$$n$$$ целых чисел, $$$i$$$-е из которых равно $$$g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$$$.

Примеры
Входные данные
1
10110101
Выходные данные
3
Входные данные
3
1111
1
0
Выходные данные
2
3
3
Входные данные
6
10110101
100100001110
0000001100010001
1111
1001010100101010101001
000100000010101111
Выходные данные
3
561
1466229
9887505
972227653
52128355