Перед вами $$$n$$$ стопок монет. Во всех стопках, кроме одной, каждая монета весит ровно $$$x$$$ миллиграмм, а в оставшейся стопке каждая монета весит ровно $$$y$$$ миллиграмм. Далее будем называть эту стопку фальшивой.
Вам нужно определить номер фальшивой стопки.
У вас есть сверхточные весы, на которые можно положить любое количество монет из любых стопок и они покажут их точный суммарный вес. Однако батарея весов быстро садится при использовании, так что вы хотите обойтись минимальным количеством взвешиваний.
Скользо взвешиваний нужно сделать, чтобы гарантированно определить номер фальшивой стопки?
В первой строке ввода дано единственное целое число $$$n$$$ $$$(2 \le n \le 200\,000)$$$ — количество стопок с монетами.
Во второй строке даны два целых числа $$$x$$$ и $$$y$$$ $$$(1 \le x, y \le 10^9, x \neq y)$$$ — веса монет в обычных и фальшивой стопках соответственно.
В третьей строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — количества монет в соответствующих стопках.
Выведите единственное число — минимальное количество взвешиваний, которое необходимо, чтобы гарантированно определить номер фальшивой стопки.
2 1 2 1 1
1
3 2 1 1 2 1
1
4 2 3 1 1 3 1
2
В первом тесте на весы можно положить монету из первой стопки. Если показанный вес будет равен 2, то эта стопка фальшивая, иначе вторая стопка фальшивая.
Во втором тесте можно положить на весы одну монету из первой стопки и две монеты из второй стопки. Разберем случаи:
- если весы показывают 6, то все монеты на них настоящие, то есть фальшивая стопка номер 3
- если весы показывают 5, значит монета из первой стопки фальшивая
- если весы показывают 4, значит монеты из второй стопки фальшивые
В третьем примере положим на весы по монете из первых двух стопок. Если число на весах 4, значит среди них нет фальшивой монеты. Иначе - есть.
После одного взвешивания у нас осталось два варианта, какая стопка фальшивая. Положим монету из одной из них на весы и узнаем — какая она.
Мальчик Лёша очень любит задачи по информатике. Но не решать их, а читать условия. И вот, прочитав очередное условие на две с половиной страницы, он понял его формальную часть и теперь просит вас решить саму задачу:
Даны два массива $$$a$$$ и $$$b$$$ из $$$n$$$ элементов, а также число $$$m$$$. Вам нужно переставить числа во втором массиве так, чтобы минимизировать значение выражения:
$$$$$$(a_1 - b_1) \bmod m + (a_2 - b_2) \bmod m + \ldots + (a_n - b_n) \bmod m$$$$$$
$$$x \bmod m$$$ — это наименьшее неотрицательное целое число $$$y$$$, такое что $$$y = x + k \cdot m$$$, где $$$k$$$ — целое число.
Например $$$(-2) \bmod 3 = 1$$$, так как $$$-2 + 3 = 1$$$, а $$$10 \bmod 4 = 2$$$, так как $$$10 - 4 \cdot 2 = 2$$$.
Помогите Леше найти минимальное возможное значение такой суммы.
В первой строке входных данных даны два числа $$$n, m$$$ ($$$1 \leq n \leq 300\,000$$$, $$$1 \leq m \leq 10^9$$$) — размер массивов $$$a$$$ и $$$b$$$, а также число $$$m$$$, описанное в условии.
Во второй строке даны $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$) — элементы массива $$$a$$$.
В третьей строке даны $$$n$$$ чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq m$$$) — элементы массива $$$b$$$.
Выведите одно число — минимальное возможное значение описанной суммы, которое можно получить, переставив элементы массива $$$b$$$.
4 8 1 3 3 7 2 2 2 8
8
4 10 8 4 2 1 1 3 6 9
6
В первом примере при перестановке $$$b = \{8, 2, 2, 2 \}$$$ значение cуммы получается
$$$(1 - 8) \bmod m + (3 - 2) \bmod m + (3 - 2) \bmod m + (7 - 2) \bmod m = 1 + 1 + 1 + 5 = 8$$$
Во втором примере при перестановке $$$b = \{6, 3, 9, 1\}$$$ получим значение суммы
$$$(8 - 6) \bmod m + (4 - 3) \bmod m + (2 - 9) \bmod m + (1 - 1) \bmod m = 2 + 1 + 3 + 0 = 6$$$
Андрей обожает море. Именно поэтому в разгар летнего сезона он решил отправиться на пляж, взяв с собой лежак, чтобы позагорать.
Пляж представляет собой прямоугольное поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Некоторые клетки этого поля свободны, на некоторых расположены дорожки, камни, ларьки и другие несдвигаемые объекты, а так же на двух соседних по стороне клетках могут стоять лежаки, расположенные как горизонтально, так и вертикально.
Андрей надеется поставить где-то свой лежак, но вот незадача, свободных мест для него может уже не быть! Именно поэтому Андрей просит вас помочь найти ему свободное место для лежака. Лежак Андрея тоже должен занимать две соседние по стороне клетки.
Если двух соседних свободных клеток нет, то для того, чтобы освободить место для лежака, придется потревожить других туристов. Для этого вы можете делать следующие действия:
- Подойти к любому лежаку, и доставив $$$p$$$ единиц дискомфорта его хозяину, поднять лежак за одну из сторон и повернуть на $$$90$$$ градусов. Одна из половин лежака должна остаться в той же клетке, а вторая переместиться в свободную клетку. При этом во время поворота на пути лежака может быть что угодно.
Поворот лежака на $$$90$$$ градусов вокруг клетки $$$(1, 2)$$$.
- Подойти к любому лежаку, и доставив $$$q$$$ единиц дискомфорта его хозяину, подвинуть лежак вдоль его длинной стороны на одну клетку. Одна сторона лежака должна переместиться на место другой, а другая — в свободную клетку.
Сдвиг лежака на одну клетку вправо.
В любой момент времени каждый лежак занимает две соседние клетки, не содержащие ничего другого. Вы можете двигать одновременно максимум один лежак.
Помогите Андрею освободить место для еще одного лежака, доставив минимальное количество дискомфорта окружающим, или скажите, что сделать это не получится.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — количество строк и столбцов на поле.
Вторая строка содержит два целых числа $$$p$$$ и $$$q$$$ ($$$1 \le p, q \le 10^9$$$) — количество единиц дискомфорта, которые приносят поворот и сдвиг лежака, соответственно.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов, описывающие клетки поля. Все строки состоят из символов «L», «R», «D», «U», «.» и «#», задающих тип клетки. Символы «L», «R», «D» и «U» обозначают половину лежака, находящегося в этой клетке — левая, правая, нижняя или верхняя половина, соответственно. Символ «.» обозначает свободную клетку, а символ «#» — клетку, занятую несдвигаемым объектом.
Выведите одно число — минимальное количество дискомфорта, которое возникнет при освобождении места для лежака. Если освободить место для лежака невозможно, выведите число $$$-1$$$.
2 55 2.LR####LR.
4
2 34 5LR.#.#
-1
4 310 10.LR###UU#DD.
-1
3 610 7.U##.##DLR##.##LR.
24
В первом примере, передвинув верхний лежак налево, а нижний лежак направо, Андрей сможет вертикально поставить лежак посередине пляжа. Таким образом, мы доставим $$$2 + 2 = 4$$$ единицы дискомфорта. Можно показать, что доставить меньшее количество дискомфорта не получится.
 | |  |
Вам дано число $$$x$$$ и массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Нужно определить, делится ли нацело число $$$a_1! + a_2! + \ldots + a_n!$$$ на число $$$x!$$$.
За $$$k!$$$ мы обозначили факториал числа $$$k$$$ — произведение всех натуральных чисел, меньших либо равных $$$k$$$. Например $$$3! = 1 \cdot 2 \cdot 3 = 6$$$, а $$$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 500\,000$$$, $$$1 \le x \le 500\,000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le x$$$) — элементы массива.
В единственной строке выведите «Yes» (без кавычек), если $$$a_1! + a_2! + \ldots + a_n!$$$ делится нацело на $$$x!$$$, и «No» (без кавычек) в противном случае.
6 4 3 2 2 2 3 3
Yes
8 3 3 2 2 2 2 2 1 1
Yes
7 8 7 7 7 7 7 7 7
No
10 5 4 3 2 1 4 3 2 4 3 4
No
2 500000 499999 499999
No
В первом примере из условия $$$3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$$$. Число $$$24$$$ делится на $$$4! = 24$$$.
Во втором примере из условия $$$3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$$$, что делится на $$$3! = 6$$$.
В третьем примере из условия $$$7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!$$$. Нетрудно доказать, что это число не делится на $$$8!$$$.
Дано дерево (связный граф с $$$n$$$ вершинами и $$$n-1$$$ ребрами), в каждой вершине которого находится неотрицательное целое число. Назовём дерево самостоятельным, если побитовое исключающее ИЛИ всех чисел в его вершинах равно $$$0$$$. Вам нужно найти, на какое максимальное количество самостоятельных деревьев можно разбить изначальное дерево, или сказать, что разбить изначальное дерево на самостоятельные деревья невозможно.
Разбиение дерева — это удаление из него нескольких рёбер. Можно показать, что в результате такой операции граф превратится в несколько непересекающихся деревьев.
Исключающее ИЛИ — это логическая операция, обозначаемая знаком $$$\oplus$$$, которая задаётся следующей таблицей истинности:
| $$$x$$$ | $$$y$$$ | $$$x \oplus y$$$ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Побитовое исключающее ИЛИ двух неотрицательных целых чисел $$$x$$$ и $$$y$$$ тоже обозначается $$$x \oplus y$$$ и определяется следующим образом: запишем числа $$$x$$$ и $$$y$$$ в двоичной системе счисления, дополнив при необходимости более короткое из них ведущими нулями до равной длины. Тогда $$$x \oplus y$$$ это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел $$$x$$$ и $$$y$$$. Например, $$$5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$$$.
Побитовое исключающее ИЛИ нескольких чисел можно посчитать, применяя последовательно операцию $$$\oplus$$$ к предыдущему результату. Например, $$$a \oplus b \oplus c \oplus d$$$ = $$$((a \oplus b) \oplus c) \oplus d$$$. Можно показать, что результат не зависит от порядка вычисления.
В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество вершин дерева.
В следующих $$$n-1$$$ строках вводятся по 2 числа $$$u$$$ и $$$v$$$ — концы рёбер дерева.
В последней строке находятся $$$n$$$ чисел $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — числа в вершинах дерева.
В единственной строке выведите максимальное количество самостоятельных деревьев, на которое можно разбить данное дерево, или «-1», если такого разбиения не существует.
6 1 2 1 3 2 4 2 5 3 6 2 1 1 0 1 3
3
3 1 2 2 3 1 1 1
-1
В первом тесте дерево выглядит так:
Если удалить рёбра, обозначенные крестиком, то мы получим 3 самостоятельных дерева. Можно показать, что на большее количество разбить нельзя.
Маленький Миша ходит на кружок по программированию и ничего там не решает. Это может показаться странным, но когда вы узнаете, что Миша снимает сериал по Майнкрафту, все сразу встанет на свои места...
Миша, вдохновляясь застройкой Манхэттена, построил в Майнкрафте город, который можно представить в виде таблицы $$$n \times m$$$. В городе живут $$$k$$$ школьников, $$$i$$$-й школьник живет в доме, который находится на пересечении $$$x_i$$$-й строки и $$$y_i$$$-го столбца. Также у каждого школьника есть степень его агрессивности $$$w_i$$$. Так как город оказался очень большим, Миша решил территориально ограничить действия своего сериала некоторым принадлежащим таблице квадратом $$$s$$$, стороны которого параллельны осям координат и имеют длину от $$$1$$$ до $$$\min(n, m)$$$ клеток.
По сюжету главный герой приедет в город и сразу же попадет в квадрат $$$s$$$. Обладая уникальной степенью агрессивности $$$0$$$ он сможет проявить свои лидерские качества и собрать команду из спокойных, умеренных и агрессивных школьников.
Чтобы собранная команда была разносторонней, но сплоченной, агрессивности всех школьников в ней должны быть попарно различны и должны образовывать единый отрезок подряд идущих целых чисел. То есть, если внутри квадрата $$$s$$$ найдутся школьники со степенями агрессивности $$$l, l+1, \ldots, -1, 1, \ldots, r-1, r$$$, где $$$l \le 0 \le r$$$, то главный герой сможет собрать команду из $$$r-l+1$$$ человека (сам он тоже входит в эту команду).
Обратите внимание, брать в команду всех школьников из квадрата $$$s$$$ не обязательно.
Миша считает, что в команде главного героя должно быть хотя бы $$$t$$$ человек. Поэтому его интересует, сколько существует квадратов в таблице, попав в которые, главный герой сможет набрать команду как минимум из $$$t$$$ человек. Помогите Мише это посчитать.
Первая строка содержит четыре целых числа $$$n$$$, $$$m$$$, $$$k$$$ и $$$t$$$ ($$$1 \le n, m \le 40\,000$$$, $$$1 \le n \cdot m \le 40\,000$$$, $$$1 \le k \le 10^6$$$, $$$1 \le t \le k + 1$$$) — количество строк в таблице, количество столбцов, количество школьников, которые живут в городе и необходимый размер команды соответственно.
Каждая из $$$k$$$ следующих строк содержит по три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le \lvert w_i \rvert \le 10^9$$$) — номер строки и номер столбца, на пересечении которых живет $$$i$$$-й школьник, а так же степень его агрессивности.
Выведите одно целое число — количество способов выбрать квадрат $$$s$$$ таким образом, чтобы главный герой смог набрать команду, состоящую, хотя бы из $$$t$$$ человек.
2 2 1 2 1 1 2
0
2 2 2 2 1 1 1 2 2 2
2
2 2 4 2 1 1 1 1 1 -1 1 2 1 2 2 1
4
- В первом тестовом примере главный герой ни в каком выбранном квадрате $$$s$$$ не сможет набрать команду, состоящую из более чем одного человека.
Иллюстрация к первому тестовому примеру. - Во втором тестовом примере можно выбрать квадрат $$$s$$$ двумя способами, изображенными ниже, в одном из них главный герой сможет набраться команду из школьников с степенями агрессивности $$$[0, 1]$$$, а в другом — $$$[0, 1, 2]$$$. Обратите внимание на то, что вне зависимости от выбранного квадрата главный герой со степенью агрессивности $$$0$$$ всегда будет входить в команду.
Иллюстрация ко второму тестовому примеру. - В третьем тестовом примере можно выбрать квадрат $$$s$$$ четырьмя способами, изображенными ниже, в них главный герой сможет набраться команды со следующими степенями агрессивности школьников, соответственно: $$$[-1,0,1]$$$, $$$[0,1]$$$, $$$[0,1]$$$, $$$[-1, 0, 1]$$$.
Иллюстрация к третьему тестовому примеру.
Изучив все известные алгоритмы сортировки Лёша решил придумать свой собственный. Новый алгоритм он называет «split-sort». Его идея заключается в том, чтобы несколько раз применить к сортируемому массиву длины $$$n$$$ следующие три операции:
- Выбрать число $$$k$$$ от $$$1$$$ до $$$n$$$.
- Удалить некоторые $$$k$$$ элементов массива.
- Приписать удаленные элементы в начало массива в обратном порядке.
Например, для массива [5, 1, 4, 2, 3] можно выбрать $$$k = 3$$$, удалить элементы $$$[1, 4, 3]$$$, после чего массив станет равным $$$[5, 2]$$$, а затем приписать удаленные в начало в обратном порядке, после чего массив станет равным $$$[3, 4, 1, 5, 2]$$$.
Леша всё ещё изучает свойства изобретенного алгоритма. Сейчас он пытается понять, как работа алгоритма зависит от выбора числа $$$k$$$. А именно, для данной перестановки $$$p$$$ чисел $$$1, 2, \dots, n$$$ и для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ он хочет понять, какой минимальной неупорядоченности можно добиться, сделав одну операцию с данным $$$k$$$.
Перестановкой $$$p$$$ чисел $$$1, 2, \dots n$$$ называется массив $$$[p_1, p_2, \dots p_n]$$$, такой что $$$1 \le p_i \le n$$$ и $$$p_i \neq p_j$$$ при $$$i \neq j$$$
Неупорядоченностью перестановки $$$p$$$ Леша называет количество инверсий в ней, то есть количество таких пар $$$i$$$, $$$j$$$, что $$$i \lt j$$$ и $$$p_i \gt p_j$$$.
У Леши ещё очень много важных алгоритмов, которые он хочет обдумать, а потому изучение алгоритма «split-sort» он поручил вам, справитесь ли вы с такой задачей?
Первая строка содержит единственное целое число $$$n$$$ $$$(1 \le n \le 300\,000)$$$ — длину перестановки.
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n, p_i \neq p_j$$$, если $$$i \neq j$$$) — элементы перестановки.
Выведите $$$n$$$ чисел, где $$$k$$$-е число равно минимальной неупорядоченности перестановки, которой можно добиться применением одной описанной выше операции с $$$k$$$ элементами.
5 5 1 4 2 3
5 4 4 4 4
5 1 2 3 4 5
0 1 3 6 10
5 3 5 1 2 4
3 2 2 3 5
В первом примере:
- При $$$k = 1$$$: выбираем элемент $$$[1]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4, 2, 3] \rightarrow [1, 5, 4, 2, 3]$$$ — $$$5$$$ пар, расположенных в неправильном порядке.
- При $$$k = 2$$$: выбираем элементы $$$[1, 2]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4, 3] \rightarrow [2, 1, 5, 4, 3]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
- При $$$k = 3$$$: выбираем элементы $$$[1, 2, 3]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4] \rightarrow [3, 2, 1, 5, 4]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
- При $$$k = 4$$$: выбираем элементы $$$[5, 1, 4, 2]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [3] \rightarrow [2, 4, 1, 5, 3]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
- При $$$k = 5$$$: выбираем элементы $$$[5, 1, 4, 2, 3]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [] \rightarrow [3, 2, 4, 1, 5]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
Недавно в самом центре Флатляндии построили $$$n$$$ невероятно красивых башен, $$$i$$$-я из которых находится в точке $$$x_i$$$ и имеет высоту $$$y_i$$$, а так же очень высокий отель в точке $$$0$$$. В отеле $$$q$$$ номеров и $$$j$$$-й из них находится на высоте $$$h_j$$$.
Хозяин отеля ещё не определился с ценами номеров. Он убежден, что чем больше башен можно увидеть из номера, тем больше за него готовы платить, а потому поручил вам для каждого номера посчитать, сколько башен можно увидеть из него.
В этой задаче можно считать, что башни — это отрезки на плоскости, с координатами концов $$$(x_i, 0)$$$ и ($$$x_i, y_i$$$) соответственно. Номер в отеле — это точка с координатами $$$(0, h_j)$$$.
Башню $$$i$$$ видно из номера отеля $$$j$$$, если на отрезке $$$\{(x_i, 0)$$$, $$$(x_i, y_i)\}$$$ есть точка $$$(a, b)$$$, такая что отрезок $$$\{(0, h_j)$$$, $$$(a, b)\}$$$ не пересекается с отрезками других башен. Иными словами — на отрезке от отеля до какой-то точки башни ничего нет.
Обратите внимание: отрезки пересекаются, если имеют хотя бы одну общую точку, в том числе если их общая точка — конец какого-то из отрезков.
В первой строке входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество построенных башен.
В следующих $$$n$$$ строках даны описания башен:
В $$$i$$$-й из них находятся два целых числа $$$x_i$$$ и $$$y_i$$$ $$$(1 \le x_i, y_i \le 10^9, x_i \neq x_j$$$ при $$$i \neq j)$$$ — позиция и высота $$$i$$$-й башни соответственно.
В следующей строке дано одно целое число $$$q$$$ $$$(1 \le q \le 200\,000)$$$ — количество номеров в отеле.
В следующих $$$q$$$ строках даны описания комнат в отеле:
В $$$j$$$-й из них находится единственное целое число $$$h_j$$$ $$$(1 \le h_j \le 10^9)$$$ — высота $$$j$$$-го номера в отеле.
Выведите $$$q$$$ чисел. Для каждой комнаты в отеле — количество башен, которые видно из неё.
3 2 1 1 2 4 4 4 3 4 1 2
2 3 1 2
4 5 4 8 3 10 7 4 4 4 4 1 8 5
2 1 4 3
В тестовом примере 1 всего 4 запроса, вот иллюстрация каждого:
 |  |
 |  |
Это сложная версия задачи. Разница между версиями заключается в том, что в этой версии массив содержит нули. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам дан массив $$$[a_1, a_2, \ldots a_n]$$$, состоящий из чисел $$$-1$$$, $$$0$$$ и $$$1$$$. Требуется предъявить разбиение этого массива на несколько отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$, обладающее следующим свойством:
- Обозначим за $$$s_i$$$ знакопеременную сумму элементов в $$$i$$$-м отрезке, то есть $$$s_i$$$ = $$$a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$$$. Например знакопеременная сумма на отрезке $$$[2, 4]$$$ в массиве $$$[1, 0, -1, 1, 1]$$$ равна $$$0 - (-1) + 1 = 2$$$.
- Сумма значений $$$s_i$$$ по всем отрезкам из разбиения должна быть равна нулю.
Обратите внимание, каждое $$$s_i$$$ не обязано равняться 0, условие стоит только на сумму $$$s_i$$$ по всем отрезкам разбиения.
Набор отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ называется разбиением массива $$$a$$$ длины $$$n$$$, если $$$1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$$$, причем для всех $$$i = 1, 2, \ldots k-1$$$ выполняется $$$r_i + 1 = l_{i+1}$$$. Иными словами, каждый элемент массива должен принадлежать ровно одному отрезку.
Требуется предъявить разбиение массива, обладающее описанными свойствами, или сказать, что такого разбиения не существует.
Обратите внимание, минимизировать количество отрезков в разбиении не требуется.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следуют описания наборов:
Первая строка каждого описания содержит единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — длину массива $$$a$$$.
Вторая строка каждого описания содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i$$$ равно $$$-1$$$, $$$0$$$ или $$$1$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.
Для каждого набора входных данных выведите целое число $$$k$$$ — количество отрезков в получившемся разбиении. Если требуемого разбиения не существует, выведите $$$-1$$$.
Далее, если разбиение существует, то в $$$i$$$-й из следующих $$$k$$$ строк выведите два целых числа $$$l_i$$$ и $$$r_i$$$ — границы $$$i$$$-го отрезка. При этом должны выполняться условия:
- $$$l_i \le r_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$k$$$.
- $$$l_{i + 1} = r_i + 1$$$ для всех $$$i$$$ от $$$1$$$ до $$$(k - 1)$$$.
- $$$l_1 = 1, r_k = n$$$.
Если существует несколько корректных разбиений массива на отрезки, разрешается вывести любое из них.
540 0 0 07-1 1 0 1 0 1 050 -1 1 0 131 0 111
4 1 1 2 2 3 3 4 4 4 1 1 2 2 3 5 6 7 -1 2 1 1 2 3 -1
В первом наборе входных данных массив можно просто разбить на $$$4$$$ отрезка по одному элементу, равному $$$0$$$. Тогда общая сумма будет равна $$$0 + 0 + 0 + 0 = 0$$$.
Во втором наборе входных данных массив разбивается на $$$4$$$ отрезка. На первом из них знакопеременная сумма будет равна $$$-1$$$, на втором $$$1$$$, на третьем $$$0 - 1 + 0 = -1$$$, на четвёртом $$$1 - 0 = 1$$$. Получаем общую сумму: $$$-1 + 1 -1 + 1 = 0$$$.
В третьем наборе входных данных можно показать, что требуемого разбиения не существует.
После двух своих любимых уроков — геометрии и информатики, маленький Игорь пришел на урок по истории и тут же уснул. Ему приснилось, что он сидит где-то на острове Самос и рисует на песке прямоугольные деревья. Прямоугольным Игорь называет дерево, в котором есть $$$3$$$ различные вершины $$$a$$$, $$$b$$$ и $$$c$$$, образующие прямоугольный треугольник, то есть такие, что $$$dist(a, b)^2 + dist(b, c)^2 = dist(a, c)^2$$$.
$$$dist(a, b)$$$ — это расстояние в дереве между вершинами $$$a$$$ и $$$b$$$, то есть количество ребер на единственном пути между ними.
Игорь сильно увелекся и нарисовал на песке очень много деревьев, и теперь для каждого из них он хочет понять, является ли оно прямоугольным. Помогите ему справиться с этой задачей, пока он не проснулся!
В первой строке вводится $$$t$$$ ($$$1 \le t \le 33\,333$$$) — количество деревьев, нарисованных Игорем. В следующих строках содержатся описания каждого дерева.
В первой строке каждого описания вводится одно целое число $$$n$$$ ($$$3 \le n \le 100\,000$$$) — количество вершин в дереве.
В следующих $$$n - 1$$$ строках вводятся по два целых числа $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — две вершины, которые соединены ребром.
Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра. Гарантируется, что сумма $$$n$$$ из всех наборов входных данных не превосходит $$$100\,000$$$.
Выведите ответ для каждого дерева:
Если в дереве нет прямоугольного треугольника, в отдельной строке выведите No.
Если хотя бы один прямоугольный треугольник есть, в первой строке выведите Yes, во второй — $$$3$$$ числа, через пробел $$$a, b, c$$$, ($$$1 \le a, b, c, \le n$$$) — номера любых $$$3$$$-х вершин, образующих прямоугольный треугольник в данном дереве. Вершины можно выводить в любом порядке. Обратите внимание, что вершины должны быть различными.
Буквы в Yes и No можно выводить в любом регистре.
231 22 3201 1212 179 1717 106 1014 2014 106 55 418 418 199 79 1515 89 1112 133 183 162 3
No Yes 2 8 20
Пояснения к примерам:
- Для первого дерева, существует только одна тройка вершин: $$$1$$$, $$$2$$$, $$$3$$$.
$$$dist(1, 2) = 1$$$, $$$dist(2, 3) = 1$$$, $$$dist(1, 3) = 2$$$. Но $$$1^2 + 1^2 \neq 2^2$$$ и $$$1^2 + 2^2 \neq 1^2$$$, а значит, эти $$$3$$$ вершины не образуют прямоугольный треугольник.
Следовательно, это дерево не является прямоугольным.
- Во втором дереве есть прямоугольные треугольники. Например: $$$2$$$, $$$8$$$, $$$20$$$.
$$$dist(2, 8) = 10$$$, $$$dist(2, 20) = 8$$$, $$$dist(8, 20) = 6$$$, и $$$6^2 + 8^2 = 10^2$$$.
Следовательно, это дерево является прямоугольным.
Перестановка $$$p$$$ чисел $$$1, 2, \ldots n$$$ называется почти отсортированной, если для любых трёх подряд идущих элементов в ней, первый не является максимальным. Иными словами, для любого $$$1 \leq i \leq n - 2$$$ не может одновременно выполняться, что $$$p_i \gt p_{i + 1}$$$ и $$$p_{i} \gt p_{i + 2}$$$.
Например, перестановка $$$[3, 1, 4, 2]$$$ — почти отсортирована, а $$$[3, 1, 2, 4]$$$ — нет, потому что $$$3 = \max(3, 1, 2)$$$.
От вас требуется посчитать количество почти отсортированных перестановок длины $$$n$$$, а так же суммарное количество инверсий, по всем таким перестановкам. Так как эти числа могут быть очень большими, требуется вывести их по модулю $$$10^9+7$$$.
Количеством инверсий в перестановке $$$p$$$ называется количество пар индексов $$$i, j$$$, таких что $$$1 \le i \lt j \le n$$$ и $$$p_i \gt p_j$$$.
Единственная строка входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 1\,000\,000$$$) — длины перестановок, для которых нужно посчитать ответ.
В единственной строке выведите два целых числа — количество почти отсортированных перестановок длины $$$n$$$ и сумму количества инверсий по таким перестановкам длины $$$n$$$. Оба числа требуется найти по модулю $$$10^9 + 7$$$.
1
1 0
3
4 4
153
454664696 746260713
Заметим, что в первом тестовом примере существует лишь одна перестановка длины $$$1$$$, которая по совместительству удовлетворяет требованию задачи. Из-за того что мы не можем выбрать в ней пару различных индексов получается, что она не может содержать инверсии.
Во втором тестовом примере существуют $$$4$$$ перестановки, удовлетворяющих условиям:
- $$$(1, 2, 3)$$$ — $$$0$$$ инверсий.
- $$$(1, 3, 2)$$$ — $$$1$$$ инверсия.
- $$$(2, 1, 3)$$$ — $$$1$$$ инверсия.
- $$$(2, 3, 1)$$$ — $$$2$$$ инверсии.
Вы были приглашены в качестве специалиста по оптимизации производственных процессов в одну очень крупную компанию. У компании в распоряжении находятся $$$n$$$ станков, стоящих друг за другом в цепочке производства. Каждый станок можно охарактеризовать одним из двух способов: $$$(+,~a_i)$$$ или $$$(*,~a_i)$$$.
Если на вход станку вида $$$(+,~a_i)$$$ подается заготовка с ценностью $$$x$$$, то на выходе получается заготовка с ценностью $$$x + a_i$$$.
Если на вход станку вида $$$(*,~a_i)$$$ подается заготовка с ценностью $$$x$$$, то на выходе получается заготовка с ценностью $$$x \cdot a_i$$$.
Весь производственный процесс выглядит следующим образом. На вход первому станку подается заготовка с ценностью $$$1$$$, полученная после работы первого станка заготовка подается на вход второму станку, результат его работы — на вход третьему станку и так далее. Дела у компании идут не очень хорошо, так что на данный момент ценность полученного на выходе продукта не превосходит $$$2 \cdot 10^9$$$.
Директора компании не довольны эффективностью производственного процесса и выделили вам бюджет в $$$b$$$ монет на его оптимизацию.
Чтобы оптимизировать производство, вы можете менять порядок станков в цепочке. А именно, потратив $$$p$$$ монет, вы можете взять любой станок вида $$$(+,~a_i)$$$ и переставить его в любое место в цепочке производства, не меняя порядок остальных станков. Также, потратив $$$m$$$ монет, вы можете взять любой станок вида $$$(*,~a_i)$$$ и переставить его в любое место в цепочке производства.
Какой максимальной ценности выходного продукта можно добиться, если сделать перестановки суммарной стоимостью не более $$$b$$$ монет?
Первая строка содержит четыре целых числа $$$n$$$, $$$b$$$, $$$p$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le b, p, m \le 10^9$$$) — количество станков на производстве, ваш бюджет и стоимости переноса станков обоих видов.
Каждая из следующих $$$n$$$ строк содержит описание очередного станка. Описание станка начинается с символа «+» или «*», обозначающего вид станка. Далее следует целое число $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$).
Гарантируется, что текущая ценность выходного продукта не превосходит $$$2 \cdot 10^9$$$.
Выведите одно целое число — максимальную ценность выходного продукта, которой можно добиться, переставив станки в цепи производства на не более чем $$$b$$$ монет суммарно.
3 2 1 3 * 2 + 1 + 1
6
4 2 2 2 * 2 + 1 * 3 + 2
21
8 2 1 1 * 2 + 1 * 4 + 1 + 1 + 1 * 5 + 3
240
В первом тесте бюджет не позволяет нам сдвинуть станок $$$(*,~2)$$$, однако мы можем переместить оба $$$(+,~1)$$$ в начало, и получить цепочку $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~2)$$$. Если ей на вход подать заготовку ценности $$$1$$$, то ее ценность будет меняться следующим образом: $$$1, 2, 3, 6$$$.
Во втором тесте мы можем сдвинуть только один станок. Переместим $$$(+,~2)$$$ из конца в начало получим цепочку $$$(+,~2)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(*,~3)$$$ при проходе через которую ценность заготовки меняется следующим образом: $$$1, 3, 6, 7, 21$$$.
В третьем тесте поместим станок $$$(*,~4)$$$ перед $$$(*,~5)$$$ и станок $$$(+,~3)$$$ в начало. Получим цепочку $$$(+,~3)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~4)$$$ $$$(*,~5)$$$, при проходе через которую ценность заготовки меняется так: $$$1, 4, 8, 9, 10, 11, 12, 48, 240$$$.