Перед вами $$$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$$$
Andrew loves the sea. That's why, at the height of the summer season, he decided to go to the beach, taking a sunbed with him to sunbathe.
The beach is a rectangular field with $$$n$$$ rows and $$$m$$$ columns. Some cells of the beach are free, some have roads, stones, shops and other non-movable objects. Some of two adjacent along the side cells can have sunbeds located either horizontally or vertically.
Andrew hopes to put his sunbed somewhere, but that's a bad luck, there may no longer be free places for him! That's why Andrew asked you to help him to find a free place for his sunbed. Andrew's sunbed also should be places on two adjacent cells.
If there are no two adjacent free cells, then in order to free some place for a sunbed, you will have to disturb other tourists. You can do the following actions:
- Come to some sunbed and, after causing $$$p$$$ units of discomfort to its owner, lift the sunbed by one of its sides and rotate it by $$$90$$$ degrees. One half of the sunbed must remain in the same cell and another half of the sunbed must move to the free cell. At the same time, anything could be on the way of a sunbed during the rotation .
Rotation of the sunbed by $$$90$$$ degrees around cell $$$(1, 2)$$$.
- Come to some sunbed and, after causing $$$q$$$ units of discomfort to its owner, shift the sunbed along its long side by one cell. One half of the sunbed must move to the place of another, and another — to the free cell.
Shift of the sunbed by one cell to the right.
In any moment each sunbed occupies two adjacent free cells. You cannot move more than one sunbed at a time.
Help Andrew to free a space for his sunbed, causing the minimum possible number of units of discomfort to other tourists, or detect that it is impossible.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — the number of rows and columns in rectangle.
The second line contains two integers $$$p$$$ and $$$q$$$ ($$$1 \le p, q \le 10^9$$$) — the number of units of discomfort caused by rotation and shift of a sunbed, respectively.
Each of the following $$$n$$$ lines contains $$$m$$$ characters, describing cells of the rectangle. Each lines consists of characters "L", "R", "D", "U", "." and "#", denoting the type of the cell. Characters "L", "R", "D" and "U" denote a half of a sunbed placed in the cell — left, right, bottom and top half, respectively. Character "." denotes a free cell and character "#" — a cell, occupied by some non-movable object.
Print one integer — the minimum possible number of units of discomfort, caused to other tourists, to free a space for a sunbed. If it is impossible to free a space for a sunbed, print $$$-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
In the first example we can shift upper sunbed to the left and lower sunbed — to the right. Andrew will be able to put his sunbed vertically in the middle of the beach. We well cause $$$2 + 2 = 4$$$ units of discomfort. It is easy to prove that it is an optimal answer.
 | |  |
You are given an integer $$$x$$$ and an array of integers $$$a_1, a_2, \ldots, a_n$$$. You have to determine if the number $$$a_1! + a_2! + \ldots + a_n!$$$ is divisible by $$$x!$$$.
Here $$$k!$$$ is a factorial of $$$k$$$ — the product of all positive integers less than or equal to $$$k$$$. For example, $$$3! = 1 \cdot 2 \cdot 3 = 6$$$, and $$$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$$.
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 500\,000$$$, $$$1 \le x \le 500\,000$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le x$$$) — elements of given array.
In the only line print "Yes" (without quotes) if $$$a_1! + a_2! + \ldots + a_n!$$$ is divisible by $$$x!$$$, and "No" (without quotes) otherwise.
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
In the first example $$$3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$$$. Number $$$24$$$ is divisible by $$$4! = 24$$$.
In the second example $$$3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$$$, is divisible by $$$3! = 6$$$.
In the third example $$$7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!$$$. It is easy to prove that this number is not divisible by $$$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 самостоятельных дерева. Можно показать, что на большее количество разбить нельзя.
Little Misha goes to the programming club and solves nothing there. It may seem strange, but when you find out that Misha is filming a Minecraft series, everything will fall into place...
Misha is inspired by Manhattan, so he built a city in Minecraft that can be imagined as a table of size $$$n \times m$$$. $$$k$$$ students live in a city, the $$$i$$$-th student lives in the house, located at the intersection of the $$$x_i$$$-th row and the $$$y_i$$$-th column. Also, each student has a degree of his aggressiveness $$$w_i$$$. Since the city turned out to be very large, Misha decided to territorially limit the actions of his series to some square $$$s$$$, which sides are parallel to the coordinate axes. The length of the side of the square should be an integer from $$$1$$$ to $$$\min(n, m)$$$ cells.
According to the plot, the main hero will come to the city and accidentally fall into the square $$$s$$$. Possessing a unique degree of aggressiveness $$$0$$$, he will be able to show his leadership qualities and assemble a team of calm, moderate and aggressive students.
In order for the assembled team to be versatile and close-knit, degrees of aggressiveness of all students of the team must be pairwise distinct and must form a single segment of consecutive integers. Formally, if there exist students with degrees of aggressiveness $$$l, l+1, \ldots, -1, 1, \ldots, r-1, r$$$ inside the square $$$s$$$, where $$$l \le 0 \le r$$$, the main hero will be able to form a team of $$$r-l+1$$$ people (of course, he is included in this team).
Notice, that it is not required to take all students from square $$$s$$$ to the team.
Misha thinks that the team should consist of at least $$$t$$$ people. That is why he is interested, how many squares are there in the table in which the main hero will be able to form a team of at least $$$t$$$ people. Help him to calculate this.
The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$ and $$$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$$$) — the number of rows and columns in the table, and the number of students living in the city, respectively.
Each of the following $$$k$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le \lvert w_i \rvert \le 10^9$$$) — the number of row and column, where the $$$i$$$-th student is living, and the degree of his aggressiveness.
Print one integer — the number of ways to choose the square $$$s$$$ in such way that the main hero will be able to form a team of at least $$$t$$$ people.
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
- In the first example the main hero will not be able to form a team of more than one person in any square $$$s$$$.
Illustration for the first example. - In the second example there are two ways to select square $$$s$$$. Both of them are illustrated below. In one of them the main hero will be able to form a team of students with degrees of aggressiveness $$$[0, 1]$$$, and in the another — with degrees of aggressiveness $$$[0, 1, 2]$$$. Notice, that the main hero with degree of aggressiveness $$$0$$$ will be included to the team regardless of the chosen square.
Illustration for the second example. - In the third example there are four ways to select square $$$s$$$. All of them are illustrated below. The main hero will be able to form a team with degrees of aggressiveness: $$$[-1,0,1]$$$, $$$[0,1]$$$, $$$[0,1]$$$, $$$[-1, 0, 1]$$$, respectively.
Illustration for the third example.
Изучив все известные алгоритмы сортировки Лёша решил придумать свой собственный. Новый алгоритм он называет «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 запроса, вот иллюстрация каждого:
 |  |
 |  |
This is the hard version of the problem. The difference is that in this version the array contains zeros. You can make hacks only if both versions of the problem are solved.
You are given an array $$$[a_1, a_2, \ldots a_n]$$$ consisting of integers $$$-1$$$, $$$0$$$ and $$$1$$$. You have to build a partition of this array into the set of segments $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ with the following property:
- Denote the alternating sum of all elements of the $$$i$$$-th segment as $$$s_i$$$: $$$s_i$$$ = $$$a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$$$. For example, the alternating sum of elements of segment $$$[2, 4]$$$ in array $$$[1, 0, -1, 1, 1]$$$ equals to $$$0 - (-1) + 1 = 2$$$.
- The sum of $$$s_i$$$ over all segments of partition should be equal to zero.
Note that each $$$s_i$$$ does not have to be equal to zero, this property is about sum of $$$s_i$$$ over all segments of partition.
The set of segments $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ is called a partition of the array $$$a$$$ of length $$$n$$$ if $$$1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$$$ and $$$r_i + 1 = l_{i+1}$$$ for all $$$i = 1, 2, \ldots k-1$$$. In other words, each element of the array must belong to exactly one segment.
You have to build a partition of the given array with properties described above or determine that such partition does not exist.
Note that it is not required to minimize the number of segments in the partition.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). Description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the length of array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i$$$ is $$$-1$$$, $$$0$$$, or $$$1$$$) — the elements of the given array.
It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.
For each test case print an integer $$$k$$$ — the number of segments in the partition. If required partition does not exist, print $$$-1$$$.
If partition exists, in the $$$i$$$-th of the following $$$k$$$ lines print two integers $$$l_i$$$ and $$$r_i$$$ — description of the $$$i$$$-th segment. The following conditions should be satisfied:
- $$$l_i \le r_i$$$ for each $$$i$$$ from $$$1$$$ to $$$k$$$.
- $$$l_{i + 1} = r_i + 1$$$ for each $$$i$$$ from $$$1$$$ to $$$(k - 1)$$$.
- $$$l_1 = 1, r_k = n$$$.
If there are multiple correct partitions of the array, print any of them.
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
In the first test case we can build a partition of $$$4$$$ segments — each of them will contain only one element of the array equals to $$$0$$$. So the sum will be equal to $$$0 + 0 + 0 + 0 = 0$$$.
In the second test case we can build a partition of $$$4$$$ segments. The alternating sum of the first segment will be equal to $$$-1$$$, the alternating sum of the second segment will be equal to $$$1$$$, of the third segment — $$$0 - 1 + 0 = -1$$$, of the fourth segment — $$$1 - 0 = 1$$$. The sum will be equal to $$$-1 + 1 -1 + 1 = 0$$$.
In the third test case it can be proved that the required partition does not exist.
После двух своих любимых уроков — геометрии и информатики, маленький Игорь пришел на урок по истории и тут же уснул. Ему приснилось, что он сидит где-то на острове Самос и рисует на песке прямоугольные деревья. Прямоугольным Игорь называет дерево, в котором есть $$$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$$$ инверсии.
You have been invited as a production process optimization specialist to some very large company. The company has $$$n$$$ machines at its factory, standing one behind another in the production chain. Each machine can be described in one of the following two ways: $$$(+,~a_i)$$$ or $$$(*,~a_i)$$$.
If a workpiece with the value $$$x$$$ is supplied to the machine of kind $$$(+,~a_i)$$$, then the output workpiece has value $$$x + a_i$$$.
If a workpiece with the value $$$x$$$ is supplied to the machine of kind $$$(*,~a_i)$$$, then the output workpiece has value $$$x \cdot a_i$$$.
The whole production process is as follows. The workpiece with the value $$$1$$$ is supplied to the first machine, then the workpiece obtained after the operation of the first machine is supplied to the second machine, then the workpiece obtained after the operation of the second machine is supplied to the third machine, and so on. The company is not doing very well, so now the value of the resulting product does not exceed $$$2 \cdot 10^9$$$.
The directors of the company are not satisfied with the efficiency of the production process and have given you a budget of $$$b$$$ coins to optimize it.
To optimize production you can change the order of machines in the chain. Namely, by spending $$$p$$$ coins, you can take any machine of kind $$$(+,~a_i)$$$ and move it to any place in the chain without changing the order of other machines. Also, by spending $$$m$$$ coins, you can take any machine of kind $$$(*,~a_i)$$$ and move it to any place in the chain.
What is the maximum value of the resulting product that can be achieved if the total cost of movements that are made should not exceed $$$b$$$ coins?
The first line contains four integers $$$n$$$, $$$b$$$, $$$p$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le b, p, m \le 10^9$$$) — the number of machine at the factory, your budget and costs of movements of both kinds of machines.
Each of the following $$$n$$$ lines contains description of a machine. The description begins with one of the following characters: "+" or "*", that denotes the kind of the machine. Then an integer $$$a_i$$$ follows ($$$1 \le a_i \le 2 \cdot 10^9$$$).
It's guaranteed that the current value of the resulting product does not exceed $$$2 \cdot 10^9$$$.
Print one integer — the maximum value of the resulting product that can be achieved if the total cost of movements that are made does not exceed $$$b$$$ coins.
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
In the first example our budget is too low to move machine $$$(*,~2)$$$, but we can move both machines $$$(+,~1)$$$ to the beginning of the chain. So the final chain will be $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~2)$$$. If the workpiece with the value $$$1$$$ is supplied to the first machine, its value will be changed in the following way: $$$1, 2, 3, 6$$$.
In the second example we can move only one machine. Let's move machine $$$(+,~2)$$$ to the beginning of the chain. The final chain will be $$$(+,~2)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(*,~3)$$$. The value of the workpiece will be changed in the following way: $$$1, 3, 6, 7, 21$$$.
In the third example we can place machine $$$(*,~4)$$$ before the machine $$$(*,~5)$$$, and move machine $$$(+,~3)$$$ to the beginning of the chain. The final chain will be $$$(+,~3)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~4)$$$ $$$(*,~5)$$$. The value of the workpiece will be changed in the following way: $$$1, 4, 8, 9, 10, 11, 12, 48, 240$$$.