Сотрудники лаборатории восстанавливают архив результатов эксперимента. Они знают, что записи в корректном архиве должны располагаться в неубывающем порядке значений. Однако из-за ошибки программы один непрерывный фрагмент архива мог быть сохранён в обратном порядке.
Архив представлен массивом $$$a$$$ длины $$$n$$$. За одну операцию можно выбрать два индекса $$$l$$$ и $$$r$$$ $$$(1 \le l \lt r \le n)$$$ и изменить порядок элементов подотрезка $$$a_l, a_{l+1}, \ldots, a_r$$$ на обратный.
Определите, можно ли получить неубывающий массив, выполнив не более одной операции. Если это возможно и массив ещё не отсортирован, выведите границы подходящего подотрезка. Если массив уже отсортирован, сообщите об этом отдельно. Если же получить неубывающий массив невозможно, также сообщите об этом.
В первой строке входных данных содержится число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — длина массива $$$a$$$.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — значения элементов массива $$$a$$$.
Если массив $$$a$$$ уже является неубывающим, выведите число $$$0$$$.
Если получить неубывающий массив, выполнив не более одной операции, невозможно, выведите число $$$-1$$$.
Иначе выведите границы $$$l, r (1 \le l \lt r \le n)$$$ подотрезка, для которого нужно выполнить операцию, описанную в условии задачи.
11
0
57 9 10 9 20
3 4
68 9 1 3 5 7
-1
Ювелир собирает ожерелье из разноцветных бусин и хочет немного изменить его внешний вид.
На нити расположены $$$n$$$ бусин. Цвет $$$i$$$-й бусины задаётся целым числом $$$a_i$$$. Будем считать, что ожерелье не является циклическим, то есть первая и последняя бусины не считаются соседними.
Ювелир должен выбрать ровно один цвет $$$x$$$ и удалить из ожерелья все бусины этого цвета. После этого оставшиеся бусины сдвигаются, сохраняя свой относительный порядок. При этом до выполнения операции в ожерелье должна быть хотя бы одна бусина цвета $$$x$$$.
Необходимо определить максимальное количество подряд идущих бусин одного цвета, которое может получиться после выполнения этой операции.
В первой строке входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — количество бусин в ожерелье.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — цвета бусин в порядке их расположения на нити.
В единственной строке выведите одно целое число — максимальное количество подряд идущих бусин одного цвета, которое может получиться после обязательного удаления всех бусин одного выбранного цвета.
31 1 1
0
71 2 1 3 1 1 2
3
Недавно вышедшая книга получает оценки читателей по шкале от $$$1$$$ до $$$n$$$. Читатели оставляют отзывы по очереди, а рейтинг книги в каждый момент равен среднему арифметическому всех уже поставленных оценок.
Для каждого читателя известны его тип $$$t_i$$$ и желаемый рейтинг $$$x_i$$$.
Если $$$t_i = \texttt{S}$$$, то читатель всегда ставит книге оценку $$$x_i$$$.
Если $$$t_i = \texttt{D}$$$, то перед голосованием читатель видит текущий рейтинг книги и число уже проголосовавших читателей. Затем он выбирает целую оценку от $$$1$$$ до $$$n$$$ так, чтобы рейтинг книги после его голоса был как можно ближе к $$$x_i$$$.
Организаторы могут выбрать любой порядок, в котором читатели будут оставлять отзывы.
$$$\texttt{Andrew-13}$$$ стало интересно, какими минимальным и максимальным итоговыми рейтингами может обладать книга. Найдите эти значения.
В первой строке входных данных содержится 2 числа $$$n, m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — максимальная возможная оценка книги и количество читателей соответственно.
В каждой из следующих $$$m$$$ строк содержатся символ $$$t_i$$$ ($$$t_i = \texttt{S}$$$ или $$$t_i = \texttt{D}$$$) и целое число $$$x_i$$$ $$$(1 \le x_i \le n)$$$ — тип читателя и желаемый им рейтинг.
Символ $$$t_i$$$ равен $$$\texttt{S}$$$, если читатель всегда ставит оценку $$$x_i$$$, или $$$\texttt{D}$$$, если читатель выбирает оценку так, чтобы итоговый рейтинг после его голоса был как можно ближе к $$$x_i$$$.
В единственной строке выведите два числа — минимальный и максимальный итоговые рейтинги книги.
Ваш ответ считается верным, если его абсолютная или относительная погрешность не превышает $$$10^{-9}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри – $$$b$$$. Ваш ответ считается правильным, если $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$$$.
10 3S 3S 5D 8
5.3333333333333 6.0000000000000
1000 4D 999D 101S 323D 812
487.0000000000000 606.0000000000000
На ленте в фиксированном порядке расположены $$$n$$$ коллекционных карточек. На $$$i$$$-й карточке указан номер её типа $$$a_i$$$.
Ленту можно разрезать между некоторыми соседними карточками, получив несколько непустых наборов. Порядок карточек менять нельзя, поэтому каждый набор состоит из некоторого непрерывного фрагмента ленты.
Для набора карточек определим его $$$\operatorname{MEX}$$$ как минимальный неотрицательный номер типа, который не встречается среди карточек этого набора. Например, $$$\operatorname{MEX}([0, 3, 2, 2, 0]) = 1$$$, а $$$\operatorname{MEX}([1, 2, 6]) = 0$$$.
Набор называется $$$\texttt{допустимым}$$$, если его $$$\operatorname{MEX}$$$ находится в диапазоне от $$$L$$$ до $$$R$$$ включительно.
Найдите количество способов разрезать ленту так, чтобы все получившиеся наборы были $$$\texttt{допустимыми}$$$. Так как ответ может быть большим, выведите его по модулю $$$998244353$$$.
В первой строке входных данных содержатся три целых числа $$$n$$$, $$$L$$$ и $$$R$$$ $$$(1 \le n \le 5 \cdot 10^5,\ 0 \le L \le R \le n)$$$ — количество карточек и границы допустимых значений $$$\operatorname{MEX}$$$.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le n)$$$ — номера типов карточек на ленте.
В единственной строке выведите одно число — количество способов разрезать ленту по модулю $$$998244353$$$.
5 1 30 3 1 2 0
2
6 0 20 1 0 2 3 0
24
Студент готовится к олимпиаде и собирается решить $$$n$$$ задач. Сложность $$$i$$$-й задачи равна $$$a_i$$$.
Перед началом подготовки задачи случайно перемешиваются, после чего студент решает их в получившемся порядке. Каждая из $$$n!$$$ перестановок задач равновероятна. Изначально студент не помнит решений ни одной задачи.
Для каждой задачи $$$i$$$ также известно число $$$x_i$$$ — вероятность забыть решение задачи в процентах. Тогда $$$p_i = x_i / 100$$$ вероятность забыть решение $$$i$$$-й задачи.
Решая очередную задачу $$$i$$$, студент выполняет следующие действия:
— Решает задачу $$$i$$$ и запоминает её решение.
— Получает $$$1$$$ единицу опыта за каждую задачу $$$j$$$, решение которой он помнит и для которой $$$a_j \le a_i$$$.
— Для каждой задачи $$$j \ne i$$$, решение которой он помнит, с вероятностью $$$p_j$$$ он забывает её решение. Все такие события независимы.
Таким образом, студент не может забыть решение задачи сразу после её решения. Однако после решения каждой следующей задачи он может забыть её с вероятностью, соответствующей этой задаче. Если решение задачи забыто, то до конца подготовки студент его больше не помнит.
Найдите математическое ожидание количества опыта, которое будет получено.
В первой строке входных данных содержится единственное число $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — количество задач.
В каждой из следующих $$$n$$$ строк содержатся два целых числа $$$a_i$$$ и $$$x_i$$$ $$$(1 \le a_i \le 10^9,\ 0 \le x_i \le 100)$$$ — сложность $$$i$$$-й задачи и число, задающее вероятность забыть её решение в процентах.
Значения $$$a_i$$$ не обязательно различны.
Можно показать, что математическое ожидание опыта представимо в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$q$$$ не делится на $$$998244353$$$.
В единственной строке выведите одно число — значение $$$p \cdot q^{-1}$$$ по модулю $$$998244353$$$, где $$$q^{-1}$$$ — число, обратное к $$$q$$$ по модулю $$$998244353$$$.
33 506 1001 0
915057328
51 231 782 452 893 100
154133329
Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии нужно завершить путь в начальной пещере.
Генри отправился в экспедицию в сеть пещер за древними артефактами. Вход в пещеры находится в вершине $$$1$$$, а коридоры между пещерами образуют дерево.
Генри освещает путь магической лампой. Для прохождения $$$i$$$-го коридора лампа расходует $$$w_i$$$ единиц заряда при каждом прохождении.
Однако коридоры пещер крайне неустойчивы. После двух прохождений по одному и тому же коридору его своды становятся слишком хрупкими, и в третий раз воспользоваться этим коридором уже невозможно. Поэтому Генри может пройти по каждому коридору не более двух раз, независимо от направления движения.
В каждой пещере находится артефакт. При первом посещении вершины $$$v$$$ артефакт изменяет заряд лампы на $$$a_v$$$ единиц: некоторые артефакты восстанавливают заряд (для которых $$$a_v \gt 0$$$), а другие оказываются проклятыми и, наоборот, забирают его ($$$a_v \lt 0$$$). Повторное посещение пещеры больше не влияет на заряд лампы.
В начале экспедиции Генри находится в пещере $$$1$$$ и сразу активирует находящийся в ней артефакт. Заряд лампы ни в какой момент не должен становиться отрицательным.
Генри должен посетить все пещеры и собрать все артефакты. После этого он должен вернуться в пещеру $$$1$$$ и покинуть подземелье.
Определите минимальный начальный заряд лампы, с которым Генри сможет завершить экспедицию.
В первой строке входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество пещер.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — изменения заряда лампы после первого посещения соответствующих пещер. Обратите внимание, что каждый коридор можно пройти не более двух раз вне зависимости от направления движения.
В следующих $$$n - 1$$$ строках содержатся по три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — концы $$$i$$$-го коридора и количество заряда, необходимое для его прохождения.
Гарантируется, что коридоры образуют дерево.
В единственной строке выведите одно целое число — минимальный начальный заряд лампы, с которым Генри сможет посетить все пещеры, не допуская отрицательного заряда лампы.
51 10 -2 6 71 2 101 3 23 4 13 5 7
18
42 -90 15 301 2 42 3 51 4 10
87
Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии можно завершить путь в любой пещере.
Генри отправился в экспедицию в сеть пещер за древними артефактами. Вход в пещеры находится в вершине $$$1$$$, а коридоры между пещерами образуют дерево.
Генри освещает путь магической лампой. Для прохождения $$$i$$$-го коридора лампа расходует $$$w_i$$$ единиц заряда при каждом прохождении.
Однако коридоры пещер крайне неустойчивы. После двух прохождений по одному и тому же коридору его своды становятся слишком хрупкими, и в третий раз воспользоваться этим коридором уже невозможно. Поэтому Генри может пройти по каждому коридору не более двух раз, независимо от направления движения.
В каждой пещере находится артефакт. При первом посещении вершины $$$v$$$ артефакт изменяет заряд лампы на $$$a_v$$$ единиц: некоторые артефакты восстанавливают заряд (для которых $$$a_v \gt 0$$$), а другие оказываются проклятыми и, наоборот, забирают его ($$$a_v \lt 0$$$). Повторное посещение пещеры больше не влияет на заряд лампы.
В начале экспедиции Генри находится в пещере $$$1$$$ и сразу активирует находящийся в ней артефакт. Заряд лампы ни в какой момент не должен становиться отрицательным.
Генри должен посетить все пещеры и собрать все артефакты. После этого в любой пещере он сможет активировать портал и покинуть подземелье, поэтому возвращаться ко входу не требуется.
Определите минимальный начальный заряд лампы, с которым Генри сможет завершить экспедицию.
В первой строке входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество пещер.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — изменения заряда лампы после первого посещения соответствующих пещер. Обратите внимание, что каждый коридор можно пройти не более двух раз вне зависимости от направления движения.
В следующих $$$n - 1$$$ строках содержатся по три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — концы $$$i$$$-го коридора и количество заряда, необходимое для его прохождения.
Гарантируется, что коридоры образуют дерево.
В единственной строке выведите одно целое число — минимальный начальный заряд лампы, с которым Генри сможет посетить все пещеры, не допуская отрицательного заряда лампы.
51 10 -2 6 71 2 101 3 23 4 13 5 7
16
42 -90 15 301 2 42 3 51 4 10
87