Алгоритмы

В библиотеке произошёл полтергейст! Книги на полке перепутались.  Библиотекарь хочет узнать, насколько сильно книги перепутаны.

Мера хаоса - это количество ИНВЕРСИЙ. Инверсия - это пара книг (i, j), где i < j, но книга i должна стоять ПОСЛЕ книги j (то есть номер книги i больше номера книги j).

Каждая книга имеет уникальный номер от 1 до N. Идеальный порядок: 1, 2, 3, ..., N.

Помогите библиотекарю подсчитать количество инверсий!

ВХОДНЫЕ ДАННЫЕ:
Первая строка: число N (1 ≤ N ≤ 100000) - количество книг.
Вторая строка: перестановка чисел от 1 до N - текущий порядок книг на полке.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество инверсий.
 

Задан ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.

В первой строке даны два числа \(n\) и \(m\) — количество вершин и ребер в графе соответственно (\(1 \leq n, m \leq 10^5\)). В следующих \(m\) строках заданы пары чисел \(u_i, v_i\), означающие, что в графе есть ребро из вершины \(u_i\) в вершину \(v_i\). В последней строке задана перестановка из \(n\) элементов.

Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.

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

Для упрощения первой своей конструкции Оля приняла решение рассматривать задачу в виде плоскости таким образом, что лазер будет всегда находиться в начале координат, его направление будет иметь угол кратный 45-ти градусам, а система коробов, от которых он будет отражаться, всегда будет перпендикулярна взгляду (перпендикулярна плоскости OXY). Но также стоит учесть, что короба, от которых будет отражаться свет, имеют как свойства отражения света, так и преломления, притом со всех четырёх сторон. Стоит также пренебречь в ходе расчётов тем, что луч лазера может отражаться в обратном направлении, таким образом не теряя интенсивности, а при прохождении через начало координат считаем, что он не прерывается, а летит дальше).

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

•  направление лазера, находящегося в начале координат, в виде угла наклона кратного 45 градусам (угол считается против часовой стрелке) (положительное направление оси OX равно 0 градусов, а положительное направление оси OY равно 90 градусам) (угол от 0 до 315 градусов);
•  интенсивность света лазера в нановаттах (целое число от 100 до 5000).
• На второй строке подаётся число N (1 <= N <= 20) – количество металлических коробов (параллелепипедов), которые Оля хочет установить. Далее на N строках подаются через пробел параметры каждого короба:
•  координаты левого верхнего угла, координаты правого нижнего угла короба (целые числа в диапазоне [-100;100]);
•  процент поглощения света (вещественное число в диапазоне [0; 100]).

На последней строке входных данных подаются координаты результирующей точки (целые числа в диапазоне [-100;100])

Выходные данные
Вывести в ответе в случае успеха конструкции интенсивность (только целую часть), с которой луч лазера попадёт в результирующую точку.
Если конструкция не успешна (лазер поглотился более чем на 90% от начальной интенсивности), то вывести координаты первого короба на пути лазерного луча, при отражении от которого интенсивность стала меньше 10% от начального) с указанием полученной интенсивности (только целую часть) (вывод через пробел – координаты левого верхнего угла, правого нижнего, (в том порядке, в котором короб был введена в программу), затем полученная интенсивность).
Гарантируется, что лазер не может улететь в бесконечность, то есть результатом может быть либо поглощение луча, либо попадание в результирующую точку.

Город имеет форму прямоугольника с вершинами в точках (-W,-H), (-W,H), (W,H),(W,-H).
Плоскость разбита на кварталы. Квартал — это единичная клетка, вершины которой имеют целочисленные координаты. Назовем квартал городским, если все вершины квартала находятся внутри города (считается, что точка на границе принадлежит городу). Всего в городе будет 4·W·H кварталов.
Дорожная сеть состоит из N дорог (часть дорог или все проходят через город).
Дорога — это прямая линия, не параллельная осям координат.
Дорога задается двумя различными точками на ней (точки могут находиться вне города).
Для каждого квартала определим "значимость". Значимость квартала равна количеству дорог, проходящих через этот квартал. Считается, что дорога проходит через квартал, если имеет с кварталом не менее двух общих точек.
Найдите значение "значимости" для каждого квартала. Для каждой полученной "значимости" определите количество кварталов, имеющих эту значимость.

Формат входных данных
В первой строке заданы значения W, H, N (9<W,H<201, 0<N<1001)
В следующих N строках задано по четыре числа (координаты двух точек прямой, определяющих дорогу).

Формат выходных данных
В первой строке выведите число K - количество различных ненулевых значений "значимости".
В следующих K строках выведите по два числа - значение "значимости" и количество кварталов, имеющих такое значение "значимости".


Примечание к примеру

Город расположен в прямоугольнике со сторонами 8 и 6 клеток (всего 48 кварталов)
Через город проходят 4 дороги AB, CD, EF, GH
Значимость 1 будет у 24 кварталов (коричневый цвет на рисунке)
Значимость 2 будет у 5 кварталов (зеленый цвет на рисунке)
Значимость 4 будет у 1 кварталов (красный цвет на рисунке)
18 кварталов будут иметь значимость равную 0 (на печать не выводиться)

Станция связи принимает блоки сообщений. Каждое сообщение представляет собой последовательность кодовых сигналов. Всего сигналов 26; они перечислены в блоке как цифры числа, записанного в системе с основанием 26.Обработка некоторых кодовых сигналов требует участия операторов;значения таких сигналов кратны 6. На вход подаётся N чисел, записанных вдесятичной системе счисления – блоков сообщений. Определите, в сколькихблоках оказалось менее M₁ или более M₂ команд, требующих участияоператоров.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество блоков сообщений. Во второй строке подаются два целых неотрицательных числа M₁ и M₂ (0 ≤ M₁ ≤ M₂ ≤ 1000) – ограничение по количеству кодовых сигналов, требующих обработки оператором. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*10⁹ – блок сообщений, записанных в десятичной системе счисления.
Формат выходных данных
Вывести одно целое число – в скольких блоках оказалось менее M₁ или более M₂ команд, требующих участия операторов.

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

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на \(-1\). Например, чтобы сделать массив \([-4, 4, 1, 3, -10]\) отсортированным, она может умножить на \(-1\) числа на позициях \(2\) и \(5\), и получить массив \([-4, -4, 1, 3, 10]\).

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

Помогите ей с этой задачей! Поскольку итоговое количество способов может быть слишком большим, найдите ответ по модулю \(998244353\).

В первой строке ввода записано целое число \(n\) — количество элементов в массиве (\(1 \leqslant n \leqslant 10^6\)).

Формат входных данных
Во второй строке через пробел перечислены \(n\) целых чисел \(a_1\), \(a_2\), …, \(a_n\) — элементы массива (\(-10^9 \leqslant a_i \leqslant 10^9\)).

Формат выходных данных
Выведите одно число — количество способов отсортировать массив указанным образом (по модулю \(998244353\)).

 

Недавно в город приехал известный цирк. Всего в этом цирке \(n\) акробатов, и в этот раз в честь проведения СПбКОШП 2022 они подготовили особенный номер.

Известно, что \(i\)-й акробат имеет рост \(a_i\) и вес \(b_i\). Любые три акробата могут собраться вместе и показать необычный трюк. Если трюк показывают акробаты с номерами \(i\), \(j\) и \(k\), то эффектность трюка оценивается как \(a_i b_j + a_j b_k + a_k b_i\).

Тренер акробатов считает упорядоченную тройку акробатов \((i, j, k)\) хорошей, если эффектность их трюка будет не меньше, чем если они расположатся в обратном порядке \((k, j, i)\).

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

Формат входных данных
В первой строке ввода дано целое число \(n\) — количество акробатов в цирке (\(3 \leqslant n \leqslant 1000\)).

В \(i\)-й из следующих \(n\) строк через пробел даны целые числа \(a_i\) и \(b_i\) — рост и вес \(i\)-го акробата (\(1 \leqslant a_i, b_i \leqslant 10^9\)).

Формат входных данных

Выведите через пробел \(n\) различных целых чисел от \(1\) до \(n\) — номера акробатов в том порядке, в котором их стоит расположить в ряду.

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

Аллею можно представить как прямую, и её решили украсить следующим образом — начать с сосны, чередовать лампы и сосны. В итоге на аллее будет высажено \(n + 1\) сосен и установлено \(n\) ламп.

Лампы поставили почти сразу же, причём двух типов — <<A>> и <<B>>. Лампы типа <<B>> светят всегда белым светом, а цвет лампы типа <<A>> зависит от её окружения. Если дерево, которое стоит слева от лампы, выше, чем дерево, которое стоит справа от лампы, то она загорается красным цветом, иначе синим.

Когда наконец-то доставили саженцы сосен, оказалось, что высоты всех саженцев попарно различны и принимают значения от \(1\) до \(n + 1\). Решено было разместить сосны так, чтобы количество красных и количество синих ламп были как можно ближе друг к другу.

Помогите ответственным за деревья разместить все \(n + 1\) саженцев так, чтобы разница между количеством красных и синих ламп была минимальна. Формально, если после высадки сосен будет \(r\) красных и \(b\) синих ламп, необходимо минимизировать величину \(|r-b|\).

Формат входных данных
В первой строке вводится одно единственное число \(n\) — количество ламп (\(1 \leq n \leq 2 \cdot 10^5\)). Во второй строке вводится \(n\) символов, \(i\)-й из которых равен <<A>> или <<B>> — тип \(i\)-й лампы.

Формат выходных данных
Выведите \(n + 1\) различных чисел от \(1\) до \(n + 1\) — высоты сосен при оптимальном размещении. Если оптимальных ответов несколько, можно вывести любой из них.

Иллюстрация ко второму примеру

Для наглядности, на иллюстрации красные лампы имеют формулу пятиугольника, а синие имеют форму звезды.

Тогда \(r = 1\), \(b = 1\), \(|r - b| = 0\) и это размещение будет одним из оптимальных.

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).