Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать \(n\) экзаменов.

Для каждого экзамена \(i\) известны два дня: \(a_i\) — день основной сдачи экзамена, \(b_i\) — день пересдачи (\(a_i < b_i\)). В один день Поликарп может сдавать не более одного экзамена. Для каждого экзамена Поликарп самостоятельно выбирает, в какой из двух дней его сдать. Необходимо сдать все \(n\) экзаменов.

Поликарп хочет сдать сессию как можно быстрее. Выведите минимальный номер дня, в который Поликарп сможет сдать все \(n\) экзаменов, либо выведите -1, если сдать сессию полностью невозможно.

Little C очень любит число «3». Он любит все, что с ним связано.

Сейчас он играет в игру на шахматной доске \(n \times m\). Клетку в строке \(x\) и в столбце \(y\) назовем \((x,y)\). Исходно, шахматная доска пуста. Каждый раз он ставит две шахматные фигуры на две различные пустые клетки, Манхэттенское расстояние между которыми равно \(3\). Манхэттенским расстоянием между клетками \((x_i,y_i)\) и \((x_j,y_j)\) назовем \(|x_i-x_j|+|y_i-y_j|\).

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

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

Схема, которую собрал Паша, состоит из несколько проводов. Каждый провод — это отрезок, который соединяет две точки на плоскости с целыми координатами, лежащими в диапазоне \([1, 10^9]\).

В схеме есть провода двух цветов:

• красные провода: эти провода должны иметь вид горизонтального отрезка, то есть если провод соединяет две точки \((x_1, y_1)\) и \((x_2, y_2)\), то выполнено, что \(y_1 = y_2\);
• синие провода: эти провода должны иметь вид вертикального отрезка, то есть если провод соединяет две точки \((x_1, y_1)\) и \((x_2, y_2)\), то выполнено, что \(x_1 = x_2\).

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

Недоработка Пашиной схемы состоит в том, что его провода не были изолированы, и поэтому в точках пересечения проводов разных цветов возникли искры, которые Паша увидел. Он записал все точки, в которых он увидел искру. У него получилось множество из \(n\) различных точек. После чего он разобрал схему и пошёл спать.

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

There are \(n\) cities and \(m\) two-way roads in Berland, each road connecting two distinct cities.

Recently the Berland government has made a tough decision to transfer ownership of the roads to private companies. In total, there are \(100500\) private companies in Berland, numbered by integers from \(1\) to \(100500\). After the privatization, every road should belong to exactly one company.

The anti-monopoly committee demands that after the privatization each company can own at most two roads. The urbanists of Berland also stated their opinion: each city should be adjacent to the roads owned by at most \(k\) companies.

Help the government to distribute the roads between the companies so that both conditions are satisfied. That is, each company gets at most two roads, and each city has roads of at most \(k\) distinct companies adjacent to it.

В колледже учатся \(n\) студентов, также в колледже есть \(m\) клубов, пронумерованных от \(1\) до \(m\). У каждого студента известен его потенциал \(p_i\) и номер клуба \(c_i\), членом которого он является. Изначально каждый студент является членом ровно одного клуба. Скоро в колледже состоится технический фестиваль, который продлится \(d\) дней. Каждый день в рамках фестиваля будет проведено соревнование по программированию.

Каждый день утром, ровно один студент решает покинуть свой клуб. После того как студент покинул свой клуб, он больше не присоединится ни к какому клубу снова. Каждый день в полдень, директор колледжа выбирает по одному студенту из каждого клуба (в случае если в каком-то клубе нет ни одного студента, из этого клуба не будет выбран никто) и составляет из них команду на этот день. Силой команды называется mex потенциалов студентов, которые в неё входят. Директор хочет выяснить наибольшую возможную силу команды в каждый из следующих \(d\) дней. Таким образом, каждый день директор выбирает команду так, чтобы максимизировать силу команды. Для мультимножества \(S\), его mex определён как наименьший неотрицательный элемент не входящий в \(S\). Например, mex мультимножества \(\{0, 1, 1, 2, 4, 5, 9\}\) равн \(3\), mex мультимножества \(\{1, 2, 3\}\) равен \(0\), а mex \(\varnothing\) (пустого множества) равен \(0\).

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

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

Галактика может быть представлена как неориентированный граф из \(n\) планет (вершин) и \(m\) червоточин (рёбер), каждая соединяющая две планеты.

Всего у империи есть \(s\) космических кораблей, а у повстанцев есть \(b\) баз, расположенных на различных планетах галактики.

У каждого космического корабля есть его местоположение \(x\), обозначающее индекс планеты, на которой он находится, его сила атаки \(a\) и определённый уровень топлива \(f\).

У каждой базы есть местоположение \(x\) и уровень защиты \(d\).

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

• Сила атаки космического корабля больше или равна уровня защиты базы,
• Уровень топлива космического корабля больше или равен кратчайшему расстоянию (количество червоточин) между планетой космического корабля и планетой с базой

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

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

Таким образом, для каждой атакованной базы повстанцы теряют по \(k\) золота.

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

Разумеется, фейковые базы не содержат золота, но создание одной такой базы стоит \(h\) золота.

Какое минимальное количество золота повстанцы потеряют, если они создадут оптимальное количество фейковых баз?

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

Можно привести множество примеров простых слов, в которых большое количество букв: «информатика», «клавиатура», «университет», «строительство», «консерватория», «сковородка», «холодильник», «секундомер», «подоконник», «электричество», «государство», «автомобиль» и другие. Разумеется, этот список можно продолжать до бесконечности.

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

Рассмотрим следующую формальную модель преобразования слов: будем считать, что в разговоре можно использовать n слов. Для каждого слова введем понятие его сокращенного аналога. Сокращенным аналогом произвольного слова s назовем такое слово t, которое удовлетворяет следующим условиям:

• встречается в s в качестве подпоследовательности,
• имеет длину от одного до четырех символов.

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

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

Футбольная лига недавно стартовала в Красивой долине. Всего \(n\) команд участвует в этой лиге. Пронумеруем их для удобства целыми числами от \(1\) до \(n\).

Всего будет проведено ровно \(\frac{n(n-1)}{2}\) матчей: каждая команда будет играть со всеми оставшимися командами ровно по одному разу. В каждом матче всегда есть победившая и проигравшая команда, ничьих не бывает.

После того, как все матчи будут сыграны, организаторы посчитают количество красивых троек. Тройка команд \((A, B, C)\) называется красивой, если команда \(A\) победила команду \(B\), команда \(B\) победила команду \(C\) и команда \(C\) победила команду \(A\). Мы рассматриваем только тройки различных команд, порядок команд внутри тройки имеет значение.

Красотой лиги назовем количество красивых троек.

В данный момент, \(m\) матчей уже было проведено и их результаты уже известны.

Какая максимальная красота лиги может быть в итоге, после проведения оставшихся матчей? Также найдите возможные результаты оставшихся \(\frac{n(n-1)}{2} - m\) матчей, при которых красота лиги максимально возможная.

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

Поликарп может призвать \(n\) разных существ, \(i\)-е существо изначально имеет силу \(a_i\); кроме того, когда Поликарп призывает его, оно увеличивает на \(b_i\) силу всех ранее призванных существ (исключая себя). Поликарп может призывать существ в любом порядке.

Однако под контролем Поликарпа может находиться не более \(k\) существ одновременно. Поэтому, помимо призыва существ, он может уничтожать ранее призванных существ. Каждое существо может быть призвано (а, значит, и уничтожено) не более одного раза.

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

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

Вам дано дерево с \(n\) вершинами. Вы можете изменить строение дерева с помощью следующей многошаговой операции:

1. Выберите три вершины \(a\), \(b\) и \(c\) такие, чтобы \(b\) соединена ребром и с \(a\) и с \(c\).
2. Для каждой вершины \(d\) кроме \(b\), которая соединена ребром с \(a\), удалите ребро, соединяющее \(d\) и \(a\), и добавьте ребро, соединяющее \(d\) и \(c\).
3. Удалите ребро, соединяющее \(a\) и \(b\), и добавьте ребро, соединяющее \(a\) и \(c\).

В качестве примера рассмотрим следующее дерево:

Следующая диаграмма иллюстрирует последовательность шагов, которые происходят, когда мы применяем операцию к вершинам \(2\), \(4\) и \(5\):

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

Найдите минимальное количество операций, которые необходимо выполнить, чтобы превратить дерево в звезду. Звезда  — это дерево с одной вершиной степени \(n - 1\), называемой его центром, и \(n - 1\) вершинами степени \(1\).

Вам задано \(n\) отрезков \([l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]\). Каждый отрезок одного из двух цветов: \(i\)-й отрезок покрашен в цвет \(t_i\).

Назовем пару отрезков \(i\) и \(j\) плохой, если выполняются два условия:

• \(t_i \ne t_j\);
• отрезки \([l_i, r_i]\) и \([l_j, r_j]\) пересекаются, касаются или вкладываются, т. е. существует целое число \(x\), такое, что \(x \in [l_i, r_i]\) и \(x \in [l_j, r_j]\).

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

В очередной скучный день карантина BThero принялся изучать матрицы размера \(n \times m\). Строки матрицы нумеруются от \(1\) до \(n\) сверху вниз, а столбцы нумеруются от \(1\) до \(m\) слева направо. Клетка в \(i\)-й строке и \(j\)-м столбце обозначается \((i, j)\).

Для каждой клетки \((i, j)\) матрицы у BThero были два значения:

1. ценность данной клетки, которая выражается одним положительным целым числом;
2. направление данной клетки, которое выражается одним из символов L, R, D, U. Данные символы означают переходы в соседние клетки \((i, j - 1)\), \((i, j + 1)\), \((i + 1, j)\), \((i - 1, j)\), соответственно. Никакой переход не вел за границу матрицы.

Назовем клетку \((i_2, j_2)\) достижимой из \((i_1, j_1)\), если, начав из клетки \((i_1, j_1)\) и переходя в соседнюю клетку в соответствии с направлением текущей клетки, мы рано или поздно посетим \((i_2, j_2)\).

BThero решил создать еще одну матрицу из имеющихся двух. Для клетки \((i, j)\) обозначим \(S_{i, j}\) как множество достижимых из нее клеток (включая саму клетку \((i, j)\)). Значение новой матрицы в клетке \((i, j)\) будет равно сумме ценностей всех клеток из \(S_{i, j}\).

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

Шеф Монокарп только что поставил \(n\) блюд на плиту. Он знает, что оптимальное время готовки \(i\)-го блюда равно \(t_i\) минут.

В любую положительную целую минуту \(T\) Монокарп может снять не более одного блюда с плиты. Если достать \(i\)-е блюдо в некоторую минуту \(T\), то его испорченность будет равна \(|T - t_i|\) — модуль значения разности между \(T\) и \(t_i\). Как только блюдо снято с плиты, его уже нельзя поставить обратно.

Монокарп должен снять все блюда с плиты. Какую минимальную суммарную испорченность он может получить?

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

Поликарпу досталась следующая задача: дана клетчатая полоска размером \(2 \times n\), некоторые клетки на ней заблокированы. Нужно проверить, можно ли замостить все незаблокированные клетки с помощью дощечек \(2 \times 1\) и \(1 \times 2\).

Например, если \(n = 5\) и полоска имеет следующий вид (черные клетки заблокированы):

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

А если \(n = 3\) и полоска имеет следующий вид:

То замостить свободные клетки невозможно.

Поликарп легко справился с этой задачей и получил свой новогодний подарок. А сможете ли вы решить ее?

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

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

На город готовится \(k\) атак гоблинов, в \(i\)-й атаке город атакуют \(i\) гоблинов. Цель Монокарпа — выдержать все \(k\) атак.

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

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

Если в результате атаки все залы оказались разграблены — Монокарп проигрывает. Иначе гномам удается восстановить город. Если какой-то зал оказался разграблен в ходе атаки, то в ходе следующих атак он все равно представляет интерес для гоблинов (гномы успевают восстановить его).

Перед каждой атакой у Монокарпа есть время для подготовки. Монокарп может готовиться бесконечно долго (он сам решает, когда вызвать каждую атаку), но чем дольше он готовится к атаке, тем меньше очков он получает. Если Монокарп готовился к \(i\)-й атаке \(t_i\) минут, то после нее он получает \(\max(0, x_i - t_i \cdot y_i)\) очков (естественно, если он не проигрывает).

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

Помогите Монокарпу выдержать все \(k\) атак гоблинов и набрать максимальное количество очков!

Cirno подготовила \(n\) массивов длины \(n\) каждый. Каждый массив — это перестановка из \(n\) целых чисел от \(1\) до \(n\). Эти массивы специальные: для всех \(1 \leq i \leq n\), если мы возьмем \(i\)-й элемент каждого массива и построим другой массив длины \(n\), состоящий из этих элементов, получившийся массив также будет перестановкой \(n\) чисел от \(1\) до \(n\). Другими словами, если эти \(n\) массивов расположить друг под другом, образовав матрицу с \(n\) строками и \(n\) столбцами, эта матрица будет латинским квадратом.

После этого Cirno добавила дополнительные \(n\) массивов, каждый массив также является перестановкой из \(n\) целых чисел от \(1\) до \(n\). Для всех \(1 \leq i \leq n\) существует хотя бы одна позиция \(1 \leq k \leq n\), такая что для \(i\)-го и \((n + i)\)-го массивов \(k\)-е элементы совпадают. Обратите внимание, что массивы с индексами от \(n + 1\) до \(2n\) не обязаны образовывать латинский квадрат.

Также Cirno убедилась, что среди \(2n\) массивов никакие два не равны, то есть для всех пар индексов \(1 \leq i < j \leq 2n\) существует хотя бы одна позиция \(1 \leq k \leq n\), такая что в \(i\)-м и \(j\)-м массивах \(k\)-е элементы различны.

В конце Cirno произвольно поменяла порядок, в котором расположены подготовленные \(2n\) массивов.

AquaMoon называет подмножество всех \(2n\) массивов размера \(n\) хорошим, если эти массивы образуют латинский квадрат.

AquaMoon хочет узнать, сколько хороших подмножеств существует. Поскольку это количество может быть очень большим, найдите его по модулю \(998\,244\,353\). Также она хочет найти любое хорошее подмножество. Можете ли вы помочь ей?

В местном бридж-клубе сейчас спорят на \(n\) различных тем, пронумерованных от \(0\) до \(n-1\), и, вот совпадение, в клубе состоят ровно \(2^n\) игроков, пронумерованных от \(0\) до \(2^n-1\). Никакие два игрока не имеют полностью совпадающих взглядов на все \(n\) тем, а именно, у \(i\)-го игрока положительный взгляд на \(j\)-ю тему, если \(i\ \&\ 2^j > 0\), и отрицательный взгляд иначе. Здесь \(\&\) обозначает операцию побитового И.

Вы хотите организовать турнир по бриджу, в котором примут участие не более чем \(k\) пар игроков (в бридж играют командами из двух игроков). Вы можете составлять пары игроков произвольным образом (каждый игрок должен быть не более чем в одной паре), но с одним условием: два игрока не могут быть в одной паре, если у них различные взгляды на \(2\) или более из данных \(n\) тем.

Вы знаете, что \(i\)-й игрок заплатит вам \(a_i\) долларов, если примет участие в турнире. Вычислите максимальную сумму, которую можно получить, выбрав команды оптимальным образом.

Разница между версиями заключается в стоимости операций. Решение для одной версии не будет работать для другой!

У Алисы есть таблица размером \(n \times m\), изначально все ее клетки окрашены в белый цвет. Клетка на пересечении \(i\)-й строки и \(j\)-го столбца обозначается как \((i, j)\). Алиса может выполнять следующие операции:

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

  Эта операция стоит \(1\) монету.

• Выбрать любой подпрямоугольник, содержащий клетку \((n, 1)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(3\) монеты.

• Выбрать любой подпрямоугольник, содержащий клетку \((1, m)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(4\) монеты.

• Выбрать любой подпрямоугольник, содержащий клетку \((n, m)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(2\) монеты.

Напомним, что подпрямоугольник — это все клетки \((x, y)\) с \(x_1 \le x \le x_2\), \(y_1 \le y \le y_2\) для некоторых \(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\).

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

Вам задан массив \(a\), состоящий из \(n\) неотрицательных целых чисел.

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

Назовем мерой полученного массива количество чисел \(k\) от \(1\) по \(n\), для которых выполняется следующее условие: существует пара соседних элементов, равных \(k\) (т. е. существует некоторый \(i \in [1, n - 1]\) такой, что \(a_i = a_{i + 1} = k\)). Если для какого-то числа \(k\) существует несколько пар соседей, то число все равно учитывается в мере только один раз.

Ваша задача — получить массив с максимально возможной мерой.

Дан неориентированный граф, состоящий из \(n\) вершин, пронумерованных от \(1\) до \(n\). Вершина \(i\) имеет значение \(a_i\), все \(a_i\) попарно различны. Между вершинами \(u\) и \(v\) есть ребро, если либо \(a_u\) делит \(a_v\), либо \(a_v\) делит \(a_u\).

Найдите минимальное количество вершин, которое нужно удалить, чтобы граф стал двудольным. При удалении вершины удаляются все инцидентные ей ребра.

Обозначим размер максимального паросочетания в графе \(G\) как \(\mathit{MM}(G)\).

Задан двудольный граф. Вершины первой доли пронумерованы от \(1\) до \(n\). Вершины второй доли пронумерованы от \(n+1\) до \(2n\). Степень каждой вершины равна \(2\).

Для четверки целых чисел \((l, r, L, R)\), где \(1 \le l \le r \le n\) и \(n+1 \le L \le R \le 2n\), определим \(G'(l, r, L, R)\) как граф, который состоит из всех вершин заданного графа, которые находятся либо в отрезке \([l, r]\), либо в отрезке \([L, R]\), и всех ребер заданного графа таких, что вершины их концов принадлежат одному из этих отрезков. Другими словами, чтобы получить граф \(G'(l, r, L, R)\) из изначального графа, надо удалить все вершины \(i\) такие, что \(i \notin [l, r]\) и \(i \notin [L, R]\), и все инцидентные им ребра.

Посчитайте сумму \(\mathit{MM}(G(l, r, L, R))\) по всем наборам целых чисел \((l, r, L, R)\) таких, что \(1 \le l \le r \le n\) and \(n+1 \le L \le R \le 2n\).

На складе вашего магазина находятся n пар обуви, каждая пара характеризуется двумя целыми числами: ценой c_i и размером s_i. Известно, что именно в этот день все числа s_i различны, то есть каждого размера имеется не более одной пары.

В магазин зашли одновременно m покупателей, у покупателя номер i при себе d_i денег, а размер его ноги равен l_i. Покупатель номер i может купить себе пару номер j, если c_j ≤ d_i, а также если l_i = s_j или l_i = s_j - 1; то есть необходимо, чтобы у него было достаточно денег чтобы заплатить, а также размер ноги был в точности равен или на 1 меньше, чем размер выбранной пары.

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

Принято считать, что самый известный алгоритм нахождения наибольшего общего делителя двух чисел придумал Евклид, однако на самом деле этот алгоритм придумала именно Тётя Люсине. Вы, должно быть, уже не удивились, ведь она — величайший ум человечества. И теперь она решила модернизировать этот алгоритм, привнеся в него немного креатива. А в вас есть эта жилка креатива?

Рассмотрим алгоритм Люсине для нахождения наибольшего общего делителя, где \(t\) это некоторый список:

function Euclid(a, b):
    if a < b:
        swap(a, b)

    if b == 0:
        return a

    r = остаток от деления a на b
    if r > 0:
        добавить r в конец t

    return Euclid(b, r)

Существует массив \(p\) пар положительных целых чисел, каждое из них не больше \(m\). Изначально список \(t\) пустой. Описанная выше функция запускается на каждой паре из массива \(p\). После этого вам даётся перестановка элементов \(t\).

Вам необходимо найти массив \(p\) любого размера не больше \(2 \cdot 10^4\) такой, что по описанному алгоритму из него получится массив \(t\), или сказать, что это невозможно.

О нет, на первой же сессии Мадоке попался билет со следующей сложной задачей:

Дано число \(n\) и \(m\) пар чисел (\(v_i, u_i\)). А также есть массив \(b_1, b_2, \ldots, b_n\), изначально заполненный нулями.

Затем для каждого индекса \(i\), где \(1 \leq i \leq m\), выполняется либо \(b_{v_i} := b_{v_i} - 1\) и \(b_{u_i} := b_{u_i} + 1\), либо \(b_{v_i} := b_{v_i} + 1\) и \(b_{u_i} := b_{u_i} - 1\). Обратите внимание, что ровно одна из этих операций должна быть выполнена для каждого \(i\).

Также дан массив \(s\) размера \(n\), состоящий только из \(0\) и \(1\). И массив \(a_1, a_2, \ldots, a_n\), где гарантируется, что если \(s_i = 0\), то \(a_i = 0\).

Помогите Мадоке и определите, можно ли выполнить операции выше таким образом, чтобы для каждого \(i\), где \(s_i = 1\), выполнялось \(a_i = b_i\). И если возможно, то как это сделать.

Дан двудольный граф с \(n_1\) вершинами в первой доле, \(n_2\) вершинами во второй доле и \(m\) ребрами. Максимальное паросочетание в таком графе — максимальный по размеру набор ребер, такой, что ни одна вершина не инцидентна более чем одному выбранному ребру.

Вам нужно обрабатывать запросы двух видов к этому графу:

• \(1\) — удалить минимально возможное количество вершин так, чтобы размер максимального паросочетания уменьшился ровно на \(1\), и вывести список удаленных вершин. Затем найти любое максимальное паросочетание в полученном графе и вывести сумму номеров ребер, входящих в это паросочетание;
• \(2\) — запрос этого типа может быть задан только после запроса типа \(1\). В качестве ответа на этот запрос вы должны вывести список номеров ребер, входящих в выбранное в предыдущем запросе паросочетание.

Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на последний запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.

В этой задаче вы можете получить вердикт «Решение зависло», так как ее нужно решать в режиме online. Если это случилось, то либо вы не следуете формату вывода, либо нарушаете какое-то из ограничений задачи. Вы можете считать, что это эквивалентно вердикту «Неправильный ответ».

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

В вашем городке есть \(n\) домов, расположенных на числовой прямой в точках \(h_1, h_2, \ldots, h_n\). Вы хотите построить себе новый дом и рассматриваете два варианта, где его разместить: точки \(p_1\) и \(p_2\).

Так как вы любите ходить в гости, вы заблаговременно вычислили для обеих точек расстояния до уже существующих домов. Более формально, вы вычислили два массива \(d_1\), \(d_2\): \(d_{i, j} = \left|p_i - h_j\right|\), где \(|x|\) обозначает модуль числа \(x\).

Спустя долгое время бездействия вы забыли расположение домов \(h\) и планируемые точки \(p_1\), \(p_2\). Но в вашем дневнике нашлись два массива — \(d_1\), \(d_2\), в подлинности которых вы сомневаетесь. Также значения внутри каждого из массивов могли перемешаться, поэтому значения на одинаковых позициях массивов \(d_1\) и \(d_2\) могут соответствовать разным домам. Обратите внимание, что значения из одного массива не могли попасть в другой, иными словами, все значения в массиве \(d_1\) соответствуют расстоянию от \(p_1\) до домов, а в массиве \(d_2\) — от \(p_2\) до домов.

Обратите внимание, что расположения домов \(h_i\) и рассматриваемых вариантов \(p_j\) могли совпадать. Например, корректными являются расположения \(h = \{1, 0, 3, 3\}\), \(p = \{1, 1\}\), которым могли соответствовать уже перемешанные \(d_1 = \{0, 2, 1, 2\}\), \(d_2 = \{2, 2, 1, 0\}\).

Проверьте, существуют ли расположение домов \(h\) и планируемые точки \(p_1\), \(p_2\), для которых бы найденные массивы расстояний были корректными. Если такое возможно, найдите подходящее расположение домов и мест строительства.

There are no heroes in this problem. I guess we should have named it "To Zero".

You are given two arrays \(a\) and \(b\), each of these arrays contains \(n\) non-negative integers.

Let \(c\) be a matrix of size \(n \times n\) such that \(c_{i,j} = |a_i - b_j|\) for every \(i \in [1, n]\) and every \(j \in [1, n]\).

Your goal is to transform the matrix \(c\) so that it becomes the zero matrix, i. e. a matrix where every element is exactly \(0\). In order to do so, you may perform the following operations any number of times, in any order:

• choose an integer \(i\), then decrease \(c_{i,j}\) by \(1\) for every \(j \in [1, n]\) (i. e. decrease all elements in the \(i\)-th row by \(1\)). In order to perform this operation, you pay \(1\) coin;
• choose an integer \(j\), then decrease \(c_{i,j}\) by \(1\) for every \(i \in [1, n]\) (i. e. decrease all elements in the \(j\)-th column by \(1\)). In order to perform this operation, you pay \(1\) coin;
• choose two integers \(i\) and \(j\), then decrease \(c_{i,j}\) by \(1\). In order to perform this operation, you pay \(1\) coin;
• choose an integer \(i\), then increase \(c_{i,j}\) by \(1\) for every \(j \in [1, n]\) (i. e. increase all elements in the \(i\)-th row by \(1\)). When you perform this operation, you receive \(1\) coin;
• choose an integer \(j\), then increase \(c_{i,j}\) by \(1\) for every \(i \in [1, n]\) (i. e. increase all elements in the \(j\)-th column by \(1\)). When you perform this operation, you receive \(1\) coin.

You have to calculate the minimum number of coins required to transform the matrix \(c\) into the zero matrix. Note that all elements of \(c\) should be equal to \(0\) simultaneously after the operations.

Даны две перестановки \(a\) и \(b\), обе размера \(n\). Перестановка размера \(n\) — это массив из \(n\) элементов, в который каждое целое число от \(1\) до \(n\) входит ровно один раз. Элементы в каждой перестановке пронумерованы от \(1\) до \(n\).

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

• выбрать целое число \(i\) от \(1\) до \(n\);
• обозначим за \(x\) такое целое число, что \(a_x = i\). Поменять местами \(a_i\) и \(a_x\);
• обозначим за \(y\) такое целое число, что \(b_y = i\). Поменять местами \(b_i\) и \(b_y\).

Вы должны отсортировать обе перестановки в порядке возрастания (то есть должны выполняться условия \(a_1 < a_2 < \dots < a_n\) и \(b_1 < b_2 < \dots < b_n\)) за минимальное количество операций. Обратите внимание, что обе перестановки должны быть отсортированы после того, как вы выполните выбранную вами последовательность операций.

You are working as a manager in The ICPC Company. In the company building, there are \(N\) computers (numbered from \(1\) to \(N\)). There are \(N - 1\) cables, numbered from \(1\) to \(N - 1\), that connect all the computers into a single network. Cable \(i\) connects computer \(U_i\) and \(V_i\). Each cable can be set into emergency mode, where cable \(i\) only transfers data from computer \(U_i\) to computer \(V_i\), but not the other way around. During a disaster, it is mandatory for all cables to be in emergency mode.

Through your research, you discover a new way to determine the vulnerability of a network. You want to add zero or more new cables to the current network such that it is not vulnerable during a disaster. Your network is not vulnerable if and only if there is exactly one permutation of \(1\) to \(N\) such that \(u\) appears before \(v\) in the permutation for all cables that connect computer \(u\) and \(v\). In other words, it should have exactly one topological order.

The following illustration shows examples of not vulnerable networks and vulnerable networks.

For the not vulnerable networks, the only permutation that satisfies the requirement for the networks on the left and on the right are \([1, 2, 3]\) and \([3, 1, 2]\), respectively. Meanwhile, for the vulnerable networks, there are \(2\) permutations that satisfy the requirement for the network on the left: \([1, 2, 3]\) and \([3, 1, 2]\); while there is no permutation that satisfies the requirement for the network on the right.

You are interested in the minimum number of new cables that should be added to the current network such that it is not vulnerable during a disaster. Furthermore, you want to know, which pairs of computers should be connected by using the minimum number of cables. If there are several ways to connect, you can connect in any way of your choice. Under the given constraints, it can be proven that there exists a way to make the network not vulnerable.

Вам дан массив \(a_1, a_2, \dots, a_n\), где каждый элемент является целым числом от \(1\) до \(x\).

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

• выберите три целых числа \(l\), \(r\) и \(k\) таких, что \(1 \le l \le r \le n\), \(1 \le k \le x\) и каждый элемент \(a_i\), для которого \(l \le i \le r\), отличается от \(k\). Затем для каждого \(i \in [l, r]\) замените \(a_i\) на \(k\).

Другими словами, вы выбираете подотрезок массива и целое число от \(1\) до \(x\), которое не встречается в этом подотрезке, и заменяете каждый элемент в подотрезке на это выбранное число.

Ваша цель — сделать все элементы в массиве равными. Какое минимальное количество операций вам нужно выполнить?

You are given \(n\) disks in the plane. The center of each disk has integer coordinates, and the radius of each disk is a positive integer. No two disks overlap in a region of positive area, but it is possible for disks to be tangent to each other.

Your task is to determine whether it is possible to change the radii of the disks in such a way that:

• Disks that were tangent to each other remain tangent to each other.
• No two disks overlap in a region of positive area.
• The sum of all radii strictly decreases.

Это интерактивная задача.

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

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

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

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

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

Затем начинается игра. Интерактор и вы по очереди выводите координаты выбранных ячеек в течение \(n \times m\) ходов, причем интерактор начинает первым.

В свой ход каждый игрок (либо вы, либо интерактор) выводит два целых числа \(i\) и \(j\) (\(1 \le i \le n\), \(1 \le j \le m\)), означающие, что игрок выбрал клетку в \(i\)-й строке и \(j\)-м столбце. Эта клетка не должна быть выбрана в предыдущих раундах. Кроме того, если это не первый ход, клетка должна быть смежной по стороне хотя бы с одной ранее выбранной клеткой.

Если любой из ваших выводов некорректен, жюри выведет «-1», и вы получите вердикт Неправильный ответ.

После всех \(n \cdot m\) ходов, если сумма чисел в выбранных вами клетках не будет строго меньше суммы чисел в клетках, выбранных соперником, жюри выведет «-1» и вы получите вердикт Неправильный ответ.

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

После вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы в этой задаче отключены.

Это легкая версия задачи. Ключевое отличие между двумя версиями выделено жирным шрифтом.

Группа из \(n\) пауков собралась, чтобы обменяться плюшевыми игрушками. Изначально у каждого паука есть \(1\) плюшевая игрушка. Каждый год, если паук \(i\) имеет хотя бы одну плюшевую игрушку, он отдаст ровно одну плюшевую игрушку пауку \(r_i\). В противном случае он ничего не сделает. Обратите внимание, что все передачи плюшевых игрушек происходят одновременно. В этой версии, если у любого паука в любой момент времени больше \(1\) плюшевой игрушки, он выбросит все, кроме \(1\).

Процесс считается стабильным в текущем году, если у каждого паука количество плюшевых игрушек (до обмена в текущем году) совпадает с количеством плюшевых игрушек, которое у него было в предыдущем году (до обмена в предыдущем году). Обратите внимание, что год \(1\) никогда не может быть стабильным.

Найдите первый год, в котором процесс становится стабильным.

Никир устроился работать регулировщиком очередей в компанию «Чёрный Контур». Ему нужно будет выбирать порядок обслуживания клиентов. Всего есть \(n\) очередей, в каждой из которых изначально стоит \(0\) человек. В каждый из следующих \(n\) моментов времени происходит два последовательных события:

1. Во все очереди приходят новые клиенты. Более формально, в \(j\)-й момент времени количество людей в \(i\)-й очереди увеличивается на положительное целое число \(a_{i,j}\).
2. Никир выбирает ровно одну из \(n\) очередей, которую будут обслуживать в этот момент времени. Количество клиентов в этой очереди становится равным \(0\).

Пусть количество людей в \(i\)-й очереди после всех событий равно \(x_i\). Никир хочет, чтобы MEX\(^{\dagger}\) набора чисел \(x_1, x_2, \ldots, x_n\) был как можно больше. Помогите ему определить максимальное значение, которое он сможет получить при оптимальном порядке обслуживания очередей.

\(^{\dagger}\)Наименьшее исключенное (MEX) набора чисел \(c_1, c_2, \ldots, c_k\) определяется как наименьшее неотрицательное целое число \(y\), которое не встречается в наборе чисел \(c\).

Например:

• \(\operatorname{MEX}([2,2,1])= 0\), так как \(0\) не принадлежит массиву.
• \(\operatorname{MEX}([3,1,0,1]) = 2\), так как \(0\) и \(1\) принадлежат массиву, а \(2\) нет.
• \(\operatorname{MEX}([0,3,1,2]) = 4\), так как \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) нет.

Даны две перестановки \(p_1,p_2,\ldots,p_n\) и \(q_1,q_2,\ldots,q_n\) длины \(n\). За одну операцию вы можете выбрать два целых числа \(1\leq i,j\leq n,i\neq j\) и поменять местами \(p_i\) и \(p_j\). Стоимость операции равна \(\min (|i-j|,|p_i-p_j|)\).

Найдите минимальную стоимость последовательности операций, в результате которых для всех \(1\leq i\leq n\) выполняется равенство \(p_i = q_i\), и выведите последовательность с минимальной стоимостью.

Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).

На перемене в школьной столовой образовалась очередь из n человек, в которой стоят мальчики и девочки. Изначально ребята встали в таком порядке, в котором они забежали в столовую. Однако через некоторое время мальчикам стало неловко, что они стоят в очереди перед девочками, и они стали каждую секунду пропускать девочек вперед.

Опишем процесс более точно. Пусть позиции в очереди последовательно пронумерованы целыми числами от 1 до n, причем тот, кто стоит на позиции номер 1 обслуживается первым. Тогда, если в момент времени x на i-ой позиции стоит мальчик, а на (i + 1)-ой — девочка, то в момент времени x + 1 на i-ой позиции будет находиться девочка, а на (i + 1)-ой — мальчик. Моменты времени заданы в секундах.

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

Вам задан ориентированный ациклический граф G, состоящий из n вершин, пронумерованных от 0 до n - 1. В графе имеется n ребер, пронумерованных от 0 до n - 1. Ребро с номером i соединяет вершины i и (i + 1) mod n, при этом может быть ориентировано как в одну сторону, так и в другую.

Операция x mod y обозначает взятие остатка от деления числа x на число y.

Назовем две вершины u и v в графе G сравнимыми, если существует путь в графе из u в v, либо из v в u. Назовем антицепью множество вершин графа G, в котором любые две различные вершины не являются сравнимыми. Размером антицепи назовем количество вершин в соответствующем множестве. Назовем антицепь максимальной, если в графе нет антицепей с большим размером.

Вам требуется найти размер максимальной антицепи в графе G.

У Little X есть n различных целых чисел: p₁, p₂, ..., p_n. Он хочет так разделить все числа на два множества, A и B, чтобы выполнялись условия:

• Если число x принадлежит множеству A, то число a - x также должно принадлежать множеству A.
• Если число x принадлежит множеству B, то число b - x также должно принадлежать множеству B.

Помогите Little X разделить числа на два множества или определите, что это невозможно.

Little X на днях решил #P полную задачу за полиномиальное время. Теперь он задает эту задачу вам!

Дана особая матрица A размера n × n, ваша задача — подсчитать ее перманент по модулю 1000000007 (10⁹ + 7). Особое свойство матрицы A заключается в том, что почти все ее элементы равняются 1. Только k элементов имеют заданное значение.

Определение перманента можно найти по следующей ссылке: https://ru.wikipedia.org/wiki/Перманент

Недавно на уроке во время контрольной Мария Ивановна перехватила записку от Саши к Оле. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.

Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Саши не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.

Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Саши. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.

Обратите внимание на необычное ограничение по памяти в этой задаче.

Сотрудники MDCS (Microsoft Development Center Serbia, сербского центра разработок Майкрософта) любят вечеринки. Обычно они ходят в ночные клубы в пятницу и субботу.

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

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

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

Группа из n городов связана сетью дорог. Первоначально между любой парой городов есть двунаправленная дорога, таким образом суммарное количество дорог равно . Чтобы проехать по любой из этих дорог, требуется ровно y секунд.

Остовным деревом называется такое подмножество дорог размера n - 1, что между любой парой городов можно проехать, используя только эти дороги.

Было выбрано некоторое остовное дерево. После этого время проезда по каждой дороге остовного дерева было изменено с y на x. Обратите внимание, не гарантируется, что x меньше y.

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