Вам, как великому повелителю чисел, поручено выполнить одно архиважное задание, от которого, как утверждают древние пророчества, зависит судьба не только конкурсной таблицы, но и, быть может, всей вычислительной вселенной. $$$ \\ $$$ В некотором королевстве целых чисел обитает благородное множество $$$ S=\{1,2,3,\cdots,n\} $$$, в котором нет ни одного повторяющегося элемента — каждый житель уникален. Однако в последнее время в этом множестве начали происходить странные события. $$$ \\ $$$ Великий прорицатель, используя магические силы предсказания, заранее определил, как именно будут располагаться первые mm чисел итоговой перестановки. Эти элементы уже прочно закрепились на своих позициях в начале будущего массива — и сдвинуть их невозможно, ибо они уже запечатаны волей судьбы. $$$ \\ $$$ Ваша задача, о могучий упорядочиватель, заключается в следующем: определить порядок оставшихся $$$ n-m $$$ элементов $$$ (p_{m+1},p_{m+2},\cdots,p_{n}) $$$, так чтобы, после объединения с предсказанным префиксом, полученная перестановка $$$ p=\left[ p_1,p_2,p_3,\cdots,p_n \right] $$$ была всё ещё корректной (то есть содержала все числа от $$$ 1 $$$ до $$$ n $$$ ровно по одному разу), но при этом количество инверсий в ней было минимально возможным. $$$ \\ $$$ Определения:

• Перестановка длины $$$ n $$$ — это такой массив из $$$ n $$$ различных целых чисел от $$$ 1 $$$ до $$$ n $$$, в котором каждое число встречается ровно один раз.
• Инверсией в перестановке называют такую пару индексов $$$ (i, j) $$$, что $$$( 1 \le i \lt j \le n )$$$ и одновременно выполняется $$$ ( p_i \gt p_j ) $$$.

Вам дано футбольное поле в трёхмерном пространстве. Мяч изначально находится в точке $$$(x, y, z)$$$. Перед мячом расположены ворота — прямоугольный параллелепипед с одной вершиной в точке $$$(0, 0, 0)$$$ и противоположной в точке $$$(A, B, C)$$$.

После удара мяч начинает лететь с начальной скоростью $$$v$$$ в направлении, определяемом двумя углами:

• $$$\theta$$$ — горизонтальный угол в градусах,
• $$$\phi$$$ — вертикальный угол в градусах.

В каждый момент времени $$$t \ge 0$$$ положение мяча задаётся формулами:

$$$X(t) = x + v \cdot \cos(\phi) \cdot \cos(\theta) \cdot t$$$

$$$Y(t) = y + v \cdot \cos(\phi) \cdot \sin(\theta) \cdot t$$$

$$$Z(t) = z + v \cdot \sin(\phi) \cdot t - \frac{1}{2} \cdot g \cdot t^2$$$

где $$$g = 9.81$$$, а углы переводятся в радианы:

$$$\theta_\text{рад} = \theta \cdot \pi / 180$$$, $$$\phi_\text{рад} = \phi \cdot \pi / 180$$$.

Вам нужно определить, попадёт ли мяч когда-либо в объём ворот.

Считается, что мяч находится внутри ворот, если в некоторый момент времени $$$t \ge 0$$$ его положение $$$(X(t), Y(t), Z(t))$$$ удовлетворяет всем условиям:

$$$0 \le X(t) \le A$$$, $$$0 \le Y(t) \le B$$$, $$$0 \le Z(t) \le C$$$

В далеком будущем информация — самый ценный ресурс. Ты — элитный криптограф в Межгалактической разведке. Недавно был перехвачен бинарный сигнал $$$s$$$ длиной $$$n$$$ — предположительно, сообщение вражеской организации. По данным разведки, они используют специальный код $$$t$$$ длины $$$m$$$, который вставляется в передаваемые сигналы, чтобы передать секретные команды.

Но есть проблема: из-за космических помех часть битов могла быть случайно испорчена. Теперь перед тобой стоит важная задача: изменить минимум битов в сигнале $$$s$$$, чтобы в нем ровно $$$k$$$ раз встречалась подстрока $$$t$$$, для каждого возможного $$$k$$$ от $$$0$$$ до $$$n - m + 1$$$.

Минимальное число изменений — это количество замен 0 → 1 или 1 → 0, которые нужно сделать в $$$s$$$, чтобы точно $$$k$$$ вхождений подстроки $$$t$$$ появилось в измененной версии $$$s$$$.

Штаб-квартира ждет отчета: для каждого $$$k$$$ — какова минимальная цена (в изменениях), чтобы получить $$$k$$$ вхождений $$$t$$$?

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

> Сегмент является хорошим, если каждое различное число в нем появляется ровно одинаковое количество раз.

Вам дан массив $$$a$$$ длиной $$$n$$$, где каждый элемент представляет собой ID преподавателя, назначенного на лекцию. $$$ \\ $$$ Вам также даны $$$q$$$ запросов. Для каждого запроса вам нужно определить, является ли сегмент массива от позиции $$$l$$$ до $$$r$$$ (включительно) хорошим.

Помогите Айгерим определить, какие сегменты соответствуют правилу справедливости декана.

У студента Бекзата есть $$$n$$$ шариков. Каждый шарик либо красный (обозначается символом R), либо синий (символ B). Он выстроил их в один ряд и хочет узнать:

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

Комитет по Национальным Археологическим Исследованиям в Исследовании Организованных Зон (NARXOZ) обнаружил старинный сундук в Алматинской области. Однако на сундуке был замок с паролем, который состоит из $$$n$$$ положительных чисел.

К счастью, учёные также нашли правильную версию этого списка — ту, которая открывает сундук.

Вам даны два списка чисел: пароль, который сейчас установлен на замке, и пароль, который открывает сундук.

Чтобы изменить текущий пароль на правильный, вы можете использовать следующую операцию:

• Выберите индекс $$$i$$$ такой, что $$$1 \le i \lt n$$$.
• Пусть $$$x$$$ — значение на позиции $$$i$$$ до операции. Пусть $$$y$$$ — значение на позиции $$$i + 1$$$ до операции.
• После операции: число на позиции $$$i$$$ становится равным $$$y - 1$$$. Число на позиции $$$i + 1$$$ становится равным $$$x + 1$$$.

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

Если сделать два списка одинаковыми невозможно, выведите -1.

NARXOZ проводит конкурс: тот, кто быстрее всех решит эту задачу, получит отличное предложение о работе. Вы хотите победить — так что приступайте к работе!

В университете Narxoz профессор по алгоритмам дал студентам очередную головоломку. Он выдал массив $$$A$$$ длины $$$n$$$, записанный на доске, и массив $$$B$$$ длины $$$m$$$, который называется эталонной последовательностью.

Студенты могут применять к отрезкам массива $$$A$$$ следующую специфическую операцию очистки:

• Пока длина текущего отрезка больше $$$m$$$, разрешается выбрать позицию $$$i$$$ ($$$L \le i \lt R$$$) и удалить элемент $$$A_i$$$, но только если $$$A_i \ne A_{i+1}$$$.

Профессор хочет узнать: сколько существует таких отрезков $$$A[L..R]$$$, которые можно очистить, чтобы в результате получить массив $$$B$$$?

Помогите студентам Narxoz решить задачу и заслужить дополнительный балл на экзамене!

Два студента — Ерлан и Даулет — увлекаются математикой и любят проводить эксперименты с числами.Однажды Ерлан выбрал число $$$a$$$, а Даулет — число $$$b$$$. Вместе они решили вычислить выражение $$$a^2$$$ - $$$b^2$$$ и узнать, может ли результат быть простым числом.

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

На арене сегодня - Seduneon, и он готов пройти сквозь матрицу, чтобы достичь финального угла (n, n), выжав максимум из всех побитовых AND! $$$ \\ $$$ Задана квадратная матрица размером $$$ n \times n $$$ , состоящая из неотрицательных целых чисел. $$$ \\ $$$ Седунеон начинает в левом верхнем углу матрицы - клетке $$$(1,1)$$$ — и хочет дойти до правого нижнего угла — клетке $$$(n,n)$$$ $$$ \\ $$$ На каждом шаге он может двигаться вниз или вправо. $$$ \\ $$$ Профит пути — это побитовая операция AND всех чисел, встреченных на пути (включая начальную и конечную клетку). $$$ \\ $$$ Ваша задача — найти максимально возможный профит, который может получить седунеон, выбрав оптимальный путь.

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

Существует $$$n$$$ факультетов, расположенных в круглом здании. Это значит, что факультет $$$0$$$ является соседом факультета $$$n - 1$$$. У каждого факультета есть тип — возможно, это экономика, бизнес или даже магическая бухгалтерия — и каждый тип представлен целым числом.

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

Но иногда этого недостаточно. Поэтому разрешается строить коридоры между соседними факультетами, то есть между факультетом $$$i$$$ и $$$(i + 1) \bmod n$$$. После строительства по ним можно свободно передвигаться в обоих направлениях.

Кроме того, факультеты любят менять свой имидж. В любой момент факультет может изменить свой тип (вдруг они решили перейти на крипто-финансы).

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

• $$$1$$$ $$$i$$$ $$$x$$$ — факультет $$$i$$$ меняет свой тип на $$$x$$$;
• $$$2$$$ $$$i$$$ — между факультетом $$$i$$$ и $$$i + 1$$$ $$$mod$$$ $$$n$$$ строится коридор;
• $$$3$$$ $$$a$$$ $$$b$$$ — проверьте, можно ли добраться от факультета $$$a$$$ до факультета $$$b$$$, используя любое количество коридоров и/или порталов.

Ваша задача — для каждого запроса типа 3 вывести YES, если перемещение возможно, и NO в противном случае.