Бернарду подарили строку длины $$$N$$$, и он сразу же принялся её изучать.
Больше всего он любит искать в строке палиндромы, то есть такие подстроки, которые одинаково читаются слева направо и наоборот. Он быстро нашел все палиндромы и решил усложнить задачу. Бернард ввел термин «красивый палиндром». Красивым палиндромом он назвал строку, которая удовлетворяет следующим условиям:
Теперь Бернард хочет в подаренной ему строке найти самую длинную подстроку, являющуюся красивым палиндромом. Но эта задача оказалась достаточно сложной, поэтому он просит вас помочь ему.
Первая строка содержит целое число $$$N (2 \le N \le 5 \cdot 10^5)$$$ — длина строки.
Далее следует строка $$$S$$$ длины $$$N$$$, состоящая из строчных латинских букв.
В первой строке выведите одно целое число — длину самого длинного красивого палиндрома.
Во второй строке выведите сам палиндром. Если подходящих ответов несколько, выведите любой.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | $$$N \leq 500$$$ | $$$20$$$ | — | Полная |
| $$$2$$$ | $$$N \leq 5000$$$ | $$$40$$$ | $$$1$$$ | Полная |
| $$$3$$$ | — | $$$40$$$ | $$$1,2$$$ | Полная |
7 abaabbc
2 bb
6 abaaba
6 abaaba
6 abadbc
0
В первом примере также подойдет строка «aa».
С легкостью решив очередную задачу, Бернард решил выйти на улицу, чтобы освежиться. С удивлением он обнаружил на своём пороге математический патруль, который прибыл наказать Бернарда за систематическое нарушения законов математики. Бернард едва успел поприветствовать гостей, как патруль открыл огонь абстрактными геометрическими точками. Бернард не растерялся и достал свой абстрактный двусторонний световой меч, которым он начал вращать перед собой, отбивая летящие в него снаряды.
Меч является бесконечной прямой, которая вращается вдоль координатной плоскости вокруг центра (0,0). В начальный момент времени меч совпадает с координатной осью $$$ox$$$. Летящие в Бернарда $$$N$$$ точек перемещаются перпендикулярно плоскости, $$$i$$$-я точка представлена проекциями координат $$$X_i$$$, $$$Y_i$$$, стартовым расстоянием до плоскости $$$Z_i$$$ и скоростью перемещения $$$U_i$$$. Бернард знает, что он способен выдержать попадание нескольких точек, но обязан отбить хотя бы $$$M$$$ из них. Точка считается отбитой, есть расстояние между точкой и мечем не превосходит $$$10^{-6}$$$. Бернард может вращать меч с любой угловой скоростью, как по, так и против часовой стрелки. Угловая скорость — значение в градусах, на которое повернется меч за одну секунду. Чтобы не утомляться слишком сильно, Бернард хочет выбрать минимальную угловую скорость, которую ему не придется превышать.
Другими словами, Бернард хочет выбрать такое минимальное число $$$K$$$, чтобы выбирая в любой момент вещественную скорость вращения в градусах в диапазоне от $$$0$$$ до $$$K$$$, он мог отбить не меньше $$$M$$$ точек.
Первая строка содержит два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le M \le N \le 500)$$$ — количество точек и минимальное количество точек, которые нужно отбить.
Следующие $$$N$$$ строк содержат по четыре целых числа $$$X_i$$$, $$$Y_i$$$, $$$Z_i$$$, $$$U_i$$$ $$$(-100 \leq X_i, Y_i \leq 100)$$$, $$$(1 \leq Z_i \leq 1000)$$$, $$$(1 \leq U_i \leq 100)$$$ — координаты и скорость $$$i$$$-й точки. Скорость обозначает на сколько уменьшается $$$Z$$$ координата каждую секунду.
Выведите единственное вещественное число — минимальную угловую скорость вращения меча.
Ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.
Если отбить $$$M$$$ точек невозможно (необходимо иметь бесконечную скорость), выведите $$$-1$$$.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | $$$N \le 20$$$, $$$M = N$$$ | $$$25$$$ | — | Полная |
| $$$2$$$ | $$$N \le 200$$$, $$$M \le 50$$$ | $$$25$$$ | $$$1$$$ | Полная |
| $$$3$$$ | — | $$$50$$$ | $$$2$$$ | Полная |
5 5 1 1 5 5 0 100 4 2 -2 -2 3 3 -4 4 3 1 10 10 8 2
90.0000000000
2 2 -2 1 1 1 2 1 2 1
53.1301023542
2 2 1 1 2 2 -1 1 3 3
-1
Гарантируется, что точка не может иметь координаты $$$X=0,Y=0$$$.
Капитан математического патруля понял, что стрелять в Бернарда бесполезно и пошел врукопашную. Бернард не собирается сдаваться без боя.
Бернард знает $$$N$$$ приемов, каждый из которых является совокупностью двух одновременно происходящих действий, верхнего и нижнего. Есть три вида действия: $$$0$$$ — ожидание, $$$1$$$ — удар, $$$2$$$ — блок. Например, верхний удар означает удар в верхнюю часть тела противника, нижний блок означает защиту от нижнего удара противника. Кроме того, у каждого действия есть время исполнения $$$T$$$. В случае удара это означает, что удар достигнет цели через $$$T$$$ миллисекунд. В случае блока это означает, что любой удар в этом направлении, который произойдет после $$$T$$$-й миллисекунды, будет заблокирован. Для ожидания время не имеет значения. Все значения $$$T$$$ среди всех приемов и Бернарда, и его противника различны.
Когда удар попадает в противника, его прием прерывается. Это означает, что если оба оппонента могут ударить друг друга, побеждает тот, чей удар попал по противнику первым. Если после применения приемов все удары были заблокированы, будет ничья.
Капитан патруля знает $$$M$$$ приемов, работающих по тем же правилам. Бернард и его противник применяют один свой прием, причем капитан может применить любой прием с одинаковой вероятностью. Помогите Бернарду выбрать свой прием так, чтобы вероятность победы была наибольшей. Если таких приемов несколько, выберите среди них тот, у которого больше вероятность ничьей. Если и таких приемов несколько, выберите среди них прием с минимальным номером.
Первая строка содержит два целых числа $$$N$$$ и $$$M$$$ $$$(2 \le M \le N \le 1000)$$$ — количество приемов Бернарда и его противника.
Следующие $$$N$$$ строк содержат по четыре целых числа $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ $$$(0 \leq A, C \leq 2)$$$, $$$(1 \leq B, D \leq 10^6)$$$ — описание приемов Бернарда: номер верхнего действия, время верхнего действия, номер нижнего действия и время нижнего действия.
Следующие $$$M$$$ строк содержат по четыре целых числа $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ $$$(0 \leq A, C \leq 2)$$$, $$$(1 \leq B, D \leq 10^6)$$$ — описание приемов капитана: номер верхнего действия, время верхнего действия, номер нижнего действия и время нижнего действия. Все значения $$$B$$$ и $$$D$$$ среди всех приемов и Бернарда и его противника различны.
Выведите единственное целое число — порядковый номер лучшего приема.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | — | $$$100$$$ | — | Полная |
3 3 1 5 2 3 0 15 1 6 2 7 2 8 2 1 1 10 2 2 2 9 1 12 2 4
2
3 3 0 14 1 4 2 7 0 12 2 5 1 6 2 1 1 10 2 2 2 9 1 8 2 3
3
2 2 1 4 2 8 1 5 1 7 2 1 2 3 1 10 1 11
1
В первом тесте первый прием Бернарда против первого приема капитана приводит к ничье, т.к. капитан ставит верхний блок на 1-й миллисекунде, блокируя верхний удар на 5-й миллисекунде. В это время Бернард ставит нижний блок на 3-й миллисекунде, блокируя нижний удар капитана на 10-й миллисекунде. Первый прием Бернарда против второго приема оппонента также ничья. При этом первый прием Бернарда побеждает третий прием оппонента, потому что верхний удар на 5-й миллисекунде попадает раньше, чем удар противника на 12-й. Второй прием Бернарда побеждает первый и второй прием противника, но проигрывает третьему. Третий прием Бернарда имеет ничью со всеми приемами оппонента.
Однажды Бернард и Рудольф прогуливались по лесу. Как истинные алгоритмические программисты, они начали составлять модели попадавшихся им деревьев. Это оказалось не такой сложной задачей. Ведь основным отличием разных видов являются листья.
Лес оказался очень разнообразным. Поэтому, придя домой, Бернард и Рудольф немедленно занесли все данные в компьютер.
Они представили каждое дерево как связный неориентированный граф без циклов и петель с $$$L$$$ вершинами и $$$L - 1$$$ ребром. Затем к каждому листу соответствующего дерева они подвесили графы, характеризующие листья реальных деревьев. В их модели лист представляет собой простой цикл определенной длины не менее $$$3$$$ (контур листа), вершины которого могут быть соединены произвольным образом (жилы листа). Все листья одного дерева имеют одинаковый размер цикла.
Занеся все данные, Рудольф и Бернард задались вопросом, а сколько каких видов деревьев они обозначили. А вы сможете ответить на этот вопрос?
Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$6 \le N \le 10^6, 7 \le M \le 5 \cdot 10^6$$$) — количество вершин и ребер модели леса соответственно.
Далее следует $$$M$$$ строк, каждая из которых содержит по два числа $$$U$$$ и $$$V$$$ ($$$1\le U, V \le N, U \neq V$$$) — вершины, соединенные неориентированным ребром.
Гарантируется, что каждое дерево леса имеет хотя бы две вершины.
В первой строке выведите целое число $$$K$$$ — количество видов деревьев в лесу. Далее во второй строке выведите $$$K$$$ целых чисел через пробел — количество деревьев каждого вида в порядке возрастания.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | В лесу деревья одного типа | $$$10$$$ | — | Полная |
| $$$2$$$ | Все листья не имеют жилок | $$$30$$$ | $$$1$$$ | Полная |
| $$$3$$$ | — | $$$60$$$ | $$$2$$$ | Каждый тест |
22 26 1 2 2 6 6 7 2 7 1 3 3 4 3 5 4 8 8 9 9 4 10 5 10 11 5 11 12 13 13 17 17 18 13 18 12 14 14 15 14 16 15 19 19 20 20 15 21 16 21 22 16 22
1 2
9 12 1 7 7 8 8 9 1 9 1 2 2 3 3 4 3 5 3 6 4 5 4 6 5 6
1 1
Лес из второго примера изображен на рисунке. В нем одно дерево с двумя листьями размера 4.
Бернард приехал на соревнования по спортивному программированию, чтобы поддержать свою любимую команду.
В соревнованиях участвует всего $$$3$$$ команды. Команда Бернарда имеет номер $$$1$$$. Соревнования представляют собой серию из $$$N$$$ последовательных туров. По результатам каждого тура командам начисляются очки: за $$$1$$$-е место $$$3$$$ очка, за $$$2$$$-е — $$$2$$$, за $$$3$$$-е — $$$1$$$. Результаты всех туров суммируются, и побеждает команда, набравшая строго больше баллов, чем остальные.
После проведения всех туров члены жюри стали постепенно переносить баллы в общую таблицу результатов. Тем временем Бернард блуждал по помещению, ожидая подведения итогов. Случайно он забрел в штаб жюри и увидел частично заполненную таблицу результатов, за которой совсем никто не следил. Бернард так мечтал о победе своей команды, что решил сжульничать и подделать результаты. Он хочет заполнить оставшуюся часть таблицы так, чтобы его команда победила в соревновании. При этом, чтобы таблица не выглядела слишком подозрительно, его команда должна набрать как можно меньше очков.
В панике Бернард не мог сложить и двух чисел, поэтому он попросил вас помочь ему составить подходящую таблицу, или сообщить, что его команда не победит при любом раскладе.
Первая строка содержит целое число $$$N (1 \le N \le 100)$$$ — количество туров соревнования.
Следующие три строки содержат по $$$N$$$ символов — описание таблицы результатов. Символ в $$$i$$$-й строке, $$$j$$$-м столбце равен либо «?», если эта ячейка таблицы еще не заполнена, либо целому числу от $$$1$$$ до $$$3$$$, обозначающему номер команды, занявшей $$$i$$$-е место в $$$j$$$-м туре. Гарантируется, что таблица корректна и не содержит одинаковых команд в одном туре.
В первой строке выведите одно целое число — сумму очков, набранную командой Бернарда, если она может победить, иначе $$$-1$$$.
Если команда Бернарда может победить, в следующих трех строках выведите полностью заполненную таблицу результатов в том же формате, в котором она дана во входных данных. Таблица должна быть корректной, а также у команды Бернарда должно быть строго больше очков, чем у других. Если правильных вариантов несколько, выведите любой.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | $$$N \leq 6$$$ | $$$20$$$ | — | Полная |
| $$$2$$$ | Таблица изначально не заполнена | $$$20$$$ | — | Полная |
| $$$3$$$ | — | $$$60$$$ | $$$1,2$$$ | Полная |
5 3??13 ?333? ???22
13 31113 13331 22222
1 ? ? ?
3 1 2 3
2 3? ?3 2?
-1
У Бернарда есть натуральное число $$$N$$$. Он хочет подарить это число Рудольфу. Бернард знает, что Рудольф любит только те числа, которые делятся на число $$$M$$$. Чтобы порадовать Рудольфа, Бернард хочет поменять число $$$N$$$ таким образом, чтобы оно делилось на $$$M$$$.
За одну операцию Бернард может поменять ровно одну из цифр числа $$$N$$$. Добавлять или удалять цифры из числа запрещается. Какое наименьшее количество операций придется сделать Бернарду? Допускается, чтобы новое число содержало ведущие нули — поэтому Бернард всегда может добиться того, чтобы новое число делилось на $$$M$$$.
Первая строка содержит одно натуральное число $$$N$$$ ($$$1 \leq N \leq 10^{2000000}$$$).
Вторая строка содержит натуральное число $$$M$$$, ($$$1 \leq M \leq 10^9)$$$.
Выведите одно число — наименьшее количество операций, которое нужно будет сделать Бернарду, чтобы новое число делилось на $$$M$$$.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | $$$N \leq 10^6$$$, $$$M \leq 10^9$$$ | $$$15$$$ | — | Полная |
| $$$2$$$ | $$$N \leq 10^{5000}$$$, $$$M \leq 5000$$$ | $$$30$$$ | — | Полная |
| $$$3$$$ | $$$N \leq 10^{2000000}$$$, $$$M \leq 1000$$$ | $$$35$$$ | — | Полная |
| $$$4$$$ | $$$N \leq 10^{2000000}$$$, $$$M \leq 5000$$$ | $$$20$$$ | $$$2,3$$$ | Полная |
2023 223
2
2023 2
1
В первом примере можно, например, получить число 8028 за две операции.
Во втором примере за одну операцию можно получить число 2024.
Серия пенальти в футболе проводится по следующим правилам:
Бернард смотрит серию пенальти, но уже хочет спать. Он хочет знать, какое минимальное количество ударов будет нанесено в серии. Зная результаты всех предыдущих ударов, помогите Бернарду найти это число.
Входные данные содержат 2 непустые строки. Первая строка описывает удары первой команды, вторая — второй. Каждая строка состоит из символов 'O' (заглавная латинская буква) — гол и 'X' — удар, не приведший к голу.
Длины строк не превосходят 10. Команды наносили удары по очереди, поэтому либо длины строк равны, либо первая строка содержит на один символ больше.
Гарантируется, что описанное состояние корректно. То есть победитель еще не определен и удары наносились в соответствии с правилами, указанными в условии.
Вывести одно число — минимальное количество ударов, которое еще будет нанесено в этой серии пенальти.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | — | $$$100$$$ | — | Каждый тест |
OXO OO
3
OOOXOO XOOOOO
2
В первом примере потребуется минимум 3 удара. Например, если вторая команда забьет оба своих следующих удара, а первая команда — не забьет следующий удар, то вторая команда победит со счетом $$$4-2$$$. В этом случае больше ударов не потребуется.
Во втором примере каждая команда должна сделать еще минимум по одному удару, чтобы определить победителя.
Рудольф подарил Бернарду нового электронного питомца, называемого «Квадратный колобок». Квадратный колобок представляет собой прямоугольный параллелепипед бесконечного объема, на одной из граней которого находится прямоугольное отверстие размером $$$H \times W$$$ — рот колобка.
Колобок питается специальной прямоугольной едой, которая продается наборами. Один такой набор шел в комплекте с питомцем. Каждая порция из набора также представляет собой прямоугольный параллелепипед с измерениями $$$P_i$$$, $$$Q_i$$$ и $$$R_i$$$. Колобок может съесть и переварить порцию, если она без сжатий и трансформаций может пройти через рот колобка так, что плоскость грани параллельна плоскости рта колобка, а стороны грани параллельны границам рта колобка. По мере попадания внутрь колобка порция мгновенно трансформируется в бесформенную массу и заполняет внутреннее пространство колобка.
Бернард хочет, чтобы его питомец был всегда максимально сыт. Поэтому он докупил специальный нож, который может выполнить не более $$$K$$$ разрезов порций еды. После выполнения максимального количества разрезов нож изнашивается и больше не пригоден к использованию. Колобок способен усваивать исключительно прямоугольную еду. Поэтому разрезать порции можно только вдоль плоскости, параллельной одной из граней порции.
Теперь Бернард хочет знать, какой максимальный объем еды из имеющегося набора сможет употребить его питомец.
Первая строка содержит целые числа $$$H$$$, $$$W$$$ ($$$1 \le H, W \le 10^4$$$) — размеры рта колобка.
Вторая строка содержит целые числа $$$N$$$ и $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le K \le 2$$$) — количество порций в стартовом наборе колобка и допустимое количество разрезаний, которые можно выполнить имеющимся у Бернарда ножом.
Далее следует $$$N$$$ строк, каждая из которых содержит по три целых числа $$$P_i$$$, $$$Q_i$$$ и $$$R_i$$$ ($$$1 \le P_i, Q_i, R_i \le 10^3$$$) — размеры порций еды.
Выведите целое число $$$V$$$ — максимальный объем еды, которую сможет съесть колобок.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | $$$K = 0, 1 \le N \le 10^3$$$ | $$$15$$$ | — | Полная |
| $$$2$$$ | $$$K \le 1, 1 \le N \le 10^3$$$ | $$$25$$$ | $$$1$$$ | Полная |
| $$$3$$$ | $$$K \le 2, 1 \le N \le 10^3$$$ | $$$40$$$ | $$$2$$$ | Полная |
| $$$4$$$ | — | $$$20$$$ | $$$3$$$ | Полная |
2 3 5 0 1 2 3 2 3 4 3 4 5 4 4 2 1 1 1
31
2 3 5 1 1 2 3 2 3 4 3 4 5 4 4 2 1 1 1
91
Каждый разрез выполняется на цельном параллелепипеде. Нельзя одновременно одним разрезом разрезать две порции еды, даже если они были частями одной порции.