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

Для этого он может производить два типа разрезов:

• горизонтальный разрез, который начинается с левой стороны листа, заканчивается в правой стороне листа, проходя через весь лист параллельно верхней и нижней стороне листа;
• вертикальный разрез, который начинается с верхней стороны листа, заканчивается в нижней стороне листа, проходя через весь лист параллельно левой и правой стороне листа.

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

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

Рассмотрим два экрана, которые могут отображать последовательности заглавных латинских букв. Изначально оба экрана ничего не отображают.

За одну секунду вы можете выполнить одно из следующих двух действий:

• выбрать экран и заглавную латинскую букву, и добавить эту букву в конец последовательности, отображаемой на этом экране;
• выбрать экран и скопировать последовательность с него на другой экран, перезаписывая последовательность, которая была отображена на другом экране.

Вам нужно вычислить минимальное количество секунд, которое вам нужно потратить, чтобы первый экран отображал последовательность $$$s$$$, а второй экран отображал последовательность $$$t$$$.

У Монокарпа есть шарики, покрашенные в красный, желтый и зеленый цвета, причем среди них ровно $$$a$$$ шариков красного цвета, ровно $$$b$$$ шариков желтого цвета и ровно $$$c$$$ шариков зеленого цвета.

Монокарп может производить с шариками следующую операцию неограниченное количество раз:

• выбрать любой шарик и перекрасить его в другой цвет: красный шарик в желтый или зеленый цвет, желтый шарик в красный или зеленый цвет, зеленый шарик в красный или желтый цвет.

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

Добавлять или удалять шарики запрещено.

У Монокарпа есть массив, состоящий из $$$n$$$ целых чисел, причем $$$n$$$ является четным числом.

Монокарп должен выполнить в своем массиве ровно один обмен по следующим правилам: выбрать позицию $$$x$$$ в левой половине массива ($$$1 \le x \le \frac{n}{2}$$$), выбрать позицию $$$y$$$ в правой половине массива ($$$\frac{n}{2} + 1 \le y \le n$$$) и поменять местами элементы в позициях $$$x$$$ и $$$y$$$.

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

Недавно акшиМ столкнулся с задачей, для решения которой нужны были биномиальные коэффициенты. Он написал код, который выглядел так:

    for (int n = 0; n < N; n++) { // цикл по n от 0 до N-1 включительно
        C[n][0] = 1;
        C[n][n] = 1;
        for (int k = 1; k < n; k++) // цикл по k от 1 до n-1 включительно
            C[n][k] = C[n][k - 1] + C[n - 1][k - 1];
    }

К сожалению, он допустил ошибку, так как правильная формула следующая:

            C[n][k] = C[n - 1][k] + C[n - 1][k - 1];

Но его сокомандник, кеблидА, заинтересовался значениями, которые были получены использованием неправильной формулы. Пожалуйста, помогите ему вычислить эти коэффициенты для $$$t$$$ различных пар $$$(n_i, k_i)$$$. Обратите внимание: их необходимо вычислить в соответствии с первой (неправильной) формулой.

Поскольку значения $$$C[n_i][k_i]$$$ могут быть слишком большими, выводите их по модулю $$$10^9 + 7$$$.

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

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

Иными словами, если на предыдущем ходе Монокарп взял себе карточку, на которой записано число $$$x$$$, то на текущем ходе он может взять себе либо карточку, на которой записано число $$$x$$$, либо карточку, на которой записано число $$$x + 1$$$.

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

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

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

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

Монокарп живет в городе, который мы будем считать отрезком координатной прямой. Самая левая точка города расположена в точке $$$0$$$, а самая правая — в точке $$$10^{9}$$$.

В городе есть $$$n$$$ магазинов, расположенных в точках с целочисленными координатами, причем $$$i$$$-й магазин расположен в точке $$$a_i$$$. Гарантируется, что среди $$$n$$$ магазинов есть ровно один магазин в точке $$$0$$$ и ровно один магазин в точке $$$10^{9}$$$, а также гарантируется, что в каждой точке с целочисленными координатами есть не более одного магазина.

Правительство решило построить в городе еще $$$m$$$ магазинов. Строить новый магазин в точке, в которой уже был магазин, запрещено, а также в каждой целочисленной точке может быть построено не более одного нового магазина. Также запрещается строить магазины левее точки $$$0$$$ и правее точки $$$10^{9}$$$.

Перед вами стоит задача выбрать, где построить новые $$$m$$$ магазинов таким образом, чтобы среди всех $$$(n+m-1)$$$ пар соседних магазинов максимальное расстояние между магазинами из пары было минимально возможно. Иными словами, мы хотим минимизировать максимальную длину отрезка между двумя соседними магазинами.

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

Например, пусть строка равна «aabbbcaaadddd». В этой строке следующие блоки одинаковых букв: блок из двух букв «a», блок из трех букв «b», блок из одной буквы «c», блок из трех букв «a» и блок из четырех букв «d». Таким образом, красота этой строки равна $$$2^2 + 3^2 + 1^2 + 3^2 + 4^2 = 4 + 9 + 1 + 9 + 16 = 39$$$.

У Монокарпа есть строка $$$s$$$, состоящая из $$$n$$$ букв латинского алфавита. Он ровно один раз выберет пару соседних различных букв в строке $$$s$$$ и поменяет их местами.

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

Представьте себе игру, в которой вы играете за персонажа с двумя характеристиками: «Сила» и «Интеллект», которые изначально находятся на нулевом уровне.

В ходе игры вы получите $$$m$$$ очков характеристик, которые позволят вам поднять их уровни — одно очко увеличивает одну из характеристик на один уровень. Но в процессе игры вы также сталкиваетесь с так называемыми «Проверками характеристик»: если ваша соответствующая характеристика достаточно высока, вы пройдете проверку; в противном случае вы провалите проверку.

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

Обратите внимание, что вы не можете изменить порядок записей.

В самой популярной карточной игре в Берляндии используется колода из $$$n \times m$$$ карт. У каждой карты есть два параметра: масть и ранг. Масти в игре пронумерованы от $$$1$$$ до $$$n$$$, а ранги пронумерованы от $$$1$$$ до $$$m$$$. Для каждой комбинации масти и ранга существует ровно одна карта в колоде.

Карта с мастью $$$a$$$ и рангом $$$b$$$ может побить карту с мастью $$$c$$$ и рангом $$$d$$$ в одном из двух случаев:

• $$$a = 1$$$, $$$c \ne 1$$$ (карта масти $$$1$$$ может побить карту любой другой масти);
• $$$a = c$$$, $$$b \gt d$$$ (карта может побить любую другую карту той же масти, но ниже рангом).

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

Ваша задача — посчитать количество способов распределить карты так, чтобы выиграл первый игрок. Два способа считаются различными, если существует такая карта, что в одном она принадлежит первому игроку, а в другом — второму. Количество способов может быть очень большим, поэтому выведите его по модулю $$$998244353$$$.

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел (нумеруемых от $$$1$$$ до $$$n$$$). Изначально все они равны нулю.

Необходимо обработать $$$q$$$ запросов $$$i$$$-й запрос состоит из двух различных целых чисел $$$x_i$$$ и $$$y_i$$$. В ходе $$$i$$$-го запроса нужно выбрать целое число $$$p$$$ (которое равно либо $$$x_i$$$, либо $$$y_i$$$) и целое число $$$d$$$ (которое равно либо $$$1$$$, либо $$$-1$$$), и присвоить $$$a_p = a_p + d$$$.

После каждого запроса каждый элемент массива $$$a$$$ должен быть неотрицательным целым числом.

Необходимо обработать все запросы таким образом, чтобы сумма всех элементов массива $$$a$$$ после последнего запроса была минимально возможной.

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

Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.

Перед началом боя Монокарп раздает артефакты героям так, чтобы каждый герой получил не более одного артефакта.

Бой состоит из раундов, которые проходят следующим образом:

• сначала дракон наносит каждому герою урон, равный $$$\frac{1}{a + b}$$$ (вещественное число без округления), где $$$a$$$ — количество живых героев, а $$$b$$$ — количество активных артефактов;
• после этого все герои со здоровьем $$$0$$$ или меньше умирают;
• наконец, некоторые артефакты деактивируются. Артефакт с прочностью $$$x$$$ деактивируется, когда происходит одно из следующего: герой, держащий артефакт, либо умирает, либо получает суммарно $$$x$$$ урона (от начала боя).

Бой заканчивается, если в живых не осталось ни одного героя.

Изначально армия пуста. Приходит $$$q$$$ запросов: добавить в армию героя со здоровьем $$$x$$$ или артефакт с прочностью $$$y$$$. После каждого запроса найдите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.