Около здания университета Иннополис появилась строка, буквы которой студенты слепили из снега. Со временем некоторые буквы строки разрушились.
Один студент решил слепить новые буквы вместо разрушенных так, чтобы в полученной строке как можно чаще встречались его инициалы: двухбуквенная строка, составленная из первых букв его имени и фамилии. Считаются только те вхождения инициалов, где две буквы идут подряд. Помогите ему это сделать.
Первая строка содержит строку, состоящую из заглавных английских букв и знаков вопроса. Знаки вопроса соответствуют пропущенным буквам. Длина строки находится в диапазоне от 1 до $$$10^5$$$ символов.
Вторая строка содержит двухбуквенную строку — инициалы студента.
В первой строке выведите максимальное число раз, которое инициалы студента могут встречаться в данной строке после замены всех знаков вопроса на буквы. Во второй строке выведите саму строку. Если есть несколько ответов, выведите любой.
| Подзадача | Баллы | Ограничения |
| 1 | 60 | Инициалы студента — две одинаковые буквы |
| 2 | 40 | Нет дополнительных ограничений |
I?NO?OLIS?PE? OP
2 INNOPOLISOPEN
???? AA
3 AAAA
NONE GG
0 NONE
Юля переезжает в свой новый дом! В саду на новом месте есть две клумбы, в которых пока что нет цветов. В ближайшем цветочном магазине «Инноцвет» есть $$$n$$$ видов цветов, пронумерованных числами от $$$1$$$ до $$$n$$$.
Юля уже купила все цветы, которые планирует посадить: цветов вида $$$i$$$ было куплено ровно $$$a_i$$$ штук. При этом, дабы сделать дизайн разнообразным, Юля ограничила количество цветов следующим образом: цветов вида $$$i$$$ было куплено не менее одного и не более $$$i$$$ (то есть $$$1 \le a_i \le i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$).
Юля хочет рассадить все цветы по двум клумбам наиболее красивым образом. Для гармонии, цветы одного вида она будет сажать только в одну клумбу (все цветы одного вида должны быть высажены либо на первой клумбе, либо на второй клумбе). При этом, чтобы обеспечить максимальную симметрию, Юля хочет, чтобы число цветов на первой и второй клумбах отличалось как можно меньше.
Так как новоселье уже очень скоро, помогите Юле найти требуемую рассадку цветов!
Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — число различных видов цветов в магазине «Инноцвет».
Во второй строке находятся $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le i$$$) — число купленных цветов каждого вида.
В первой строке выведите одно целое неотрицательное число — минимальную разность количеств цветов на клумбах.
Во второй строке выведите рассадку цветов в следующем формате: $$$n$$$ чисел $$$w_1, \ldots, w_n$$$, где $$$w_i = 1$$$, если цветы вида $$$i$$$ нужно посадить в первую клумбу, и $$$w_i = 2$$$ в противном случае.
Если существует несколько рассадок с минимальной разностью количеств цветов, выведите любую.
| Подзадача | Баллы | Ограничения |
| 1 | 15 | $$$a_i = i$$$ |
| 2 | 20 | $$$n \le 16$$$ |
| 3 | 25 | $$$n \le 100$$$ |
| 4 | 40 | $$$n \le 2 \cdot 10^5$$$ |
5 1 2 1 4 3
1 1 2 1 1 2
2 1 1
0 2 1
В первом примере, на первой клумбе посажено $$$1+1+4=6$$$ цветков, а на второй — $$$2+3=5$$$ цветков, и разность количеств цветов равна $$$1$$$. Получить одинаковое количество цветов в первой и второй клумбе невозможно. Заметим, что в этом примере есть и другие оптимальные рассадки.
Во втором примере на каждой клумбе посажен один цветок, и минимальная разность равна $$$0$$$.
Рассмотрим все делители числа $$$n$$$. Нужно выбрать некоторые делители и расставить их по кругу так, чтобы отношение любых двух соседних чисел являлось простым числом.
Найдите максимальное число делителей $$$n$$$, которое можно так расставить и найдите такую расстановку.
В первой строке входных данных содержится одно число $$$n$$$ ($$$2 \le n \le 10^9$$$).
В первой строке выведите одно число $$$k$$$ — максимальное количество делителей числа $$$n$$$, которое можно расставить по кругу составить из делителей по правилам, описанным выше.
Во второй строке выведите $$$k$$$ чисел — различные делители $$$n$$$ в порядке, в котором они идут по кругу. Любые два соседних числа в этом списке, а также первое и последнее число должны отличаться домножением на простое число.
| Подзадача | Баллы | Ограничения |
| $$$1$$$ | $$$10$$$ | $$$n \le 10$$$ |
| $$$2$$$ | $$$15$$$ | $$$n \le 50$$$ |
| $$$3$$$ | $$$20$$$ | $$$n \le 150$$$ |
| $$$4$$$ | $$$20$$$ | $$$n = 10^m$$$ для целого $$$m \ge 0$$$ |
| $$$5$$$ | $$$15$$$ | $$$n = 2^x \cdot 3^y \cdot 5^z$$$ для целых $$$x, y, z \ge 0$$$ |
| $$$6$$$ | $$$10$$$ | $$$n$$$ не является квадратом целого числа |
| $$$7$$$ | $$$10$$$ | Без дополнительных ограничений |
10
4 1 2 10 5
Вы, наверно, знаете, что у каждого числа есть единственное представление в двоичной системе счисления, например, $$$21 = 16 + 4 + 1 = 10101_2$$$.
Введем понятие избыточной двоичной системы счисления. В этой системе счисления веса разрядов — также степени двойки, но в каждом разряде может стоять цифра $$$0$$$, $$$1$$$ или $$$2$$$, ведущих нулей нет. У такой системы счисления есть свои преимущества, но у одного числа может существовать несколько разных представлений: например, существует $$$5$$$ способов записать число $$$21$$$ в такой системе счисления:
- $$$21 = 16 + 4 + 1 = 10101_2$$$
- $$$21 = 16 + 2 + 2 + 1 = 10021_2$$$
- $$$21 = 8 + 8 + 4 + 1 = 2101_2$$$
- $$$21 = 8 + 8 + 2 + 2 + 1 = \textbf{2021}_2$$$
- $$$21 = 8 + 4 + 4 + 2 + 2 + 1 = 1221_2$$$
Обозначим количество способов представить число $$$n \ge 0$$$ как $$$a(n)$$$. Будем считать, что у $$$0$$$ существует одно представление, то есть, $$$a(0) = 1$$$.
Какую бы придумать задачу про $$$a(n)$$$? Вычислить $$$a(n)$$$ для заданного $$$n$$$? Не, это слишком просто. Решить «обратную» задачу: по $$$x$$$ найти $$$n$$$, что $$$a(n) = x$$$? Тоже тривиально.
Для заданных $$$x$$$ и $$$y$$$ найдите минимальное $$$n$$$, что $$$a(n) = x$$$ и $$$a(n + 1) = y$$$.
Входные данные содержат два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le 10^{18}$$$).
Если подходящего $$$n$$$ не существует, выведите $$$-1$$$. Иначе, выведите искомое минимальное $$$n$$$. Поскольку ответ может быть большим, выведите его по модулю $$$999\,999\,001$$$.
| Подзадача | Баллы | Ограничения |
| 1 | 15 | $$$x, y \le 6$$$ |
| 2 | 22 | $$$x, y \le 20$$$ |
| 4 | 34 | $$$x, y \le 10^6$$$ |
| 5 | 29 | $$$x, y \le 10^{18}$$$ |
3 1
6
5 7
21
6 2
-1