Алгоритмы

У Фермера Джона есть \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) ферм, пронумерованных от \(1\) до \(N\). Известно, что ФД закрывает ферму \(i\) в момент времени \(c_i\). Беси просыпается в момент времени \(S\) и хочет максимизировать производительность своего дня посетив как можно больше ферм, прежде чем они закроются. Она планирует посетить ферму \(i\) в момент времени \(t_i + S\). Беси должна прибыть на ферму строго раньше чем ФД закроет её, чтобы действительно посетить эту ферму.

У Беси есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. Для каждого запроса она даёт Вам два целых числа \(S\) и \(V\). Для каждого запроса выведите сможет ли Беси посетить не менее \(V\) ферм, если она проснётся в момент времени \(S\).

Фермер Джон расширяет свою ферму! Он определил совершенное место - Красно-Чёрный Лес, который состоит из \(N\) деревьев (\(1 \le N \le 10^5\)) на числовой прямой, где \(i\)-ое дерево находится в позиции \(x_i\) (\(-10^9 \le x_i \le 10^9\)).

Закон по защите окружающей среды ограничивает, какие деревья может спилить ФД, освобождая место под свою ферму. Всего имеется \(K\) ограничений (\(1 \leq K \leq 10^5\)), указывающих, что должно быть как минимум \(t_i\) деревьев на отрезке \([l_i, r_i]\), включая конечные точки (\(-10^9 \le l_i, r_i \le 10^9\)). Гарантируется, что изначально Красно-Чёрный Лес удовлетворяет этим ограничениям.

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

ПР�МЕР ВВОДА:

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

ПР�МЕР ВЫВОДА:

4
4
3

Для первого подтеста, ФД может срезать первые 4 дерева, оставив деревья в точках \(x_i = 2, 6, 7\), чтобы удовлетворить ограничениям.

Для второго подтеста, ФД дополнительные ограничения не влияют, поэтому ФД может срезать те же самые деревья.

Для третьего подтеста, ФД может срезать не более \(3\) деревьев, потому что изначально \(7\) деревьев, однако второе ограничение требует чтобы он оставил как минимум \(4\) дерева не срезанными.

Авторы: Tina Wang, Jiahe Lu, Benjamin Qi

**Замечание: Время на тест в этой задаче 4 сек, в два раза больше, чем по умолчанию.**

Вам дано целое число \(N\) (\(2\le N\le 2000\)). Рассмотрим все перестановки \([p_0,p_1,\dots, p_{N-1}]\) из \([0,1,2\dots, N-1]\).

Пусть \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) означает минимальную абсолютную разность между двумя последовательными элементами в \(p\). Также обозначим \(S_N\) множество всех таких перестановок \(p\), которые достигают максимальной возможной величины \(f(p)\).

Также Вам дополнительно дано \(K\) (\(0\le K\le N\)) ограничений вида \(p_i=j\) (\(0\le i,j<N\)). Посчитайте количество перестановок в \(S_N\), удовлетворяющих всем ограничениям, по модулю \(10^9+7\).

**Замечание: Время на тест для этой задачи 3 сек, в 1.5 больше чем по умолчанию.**

У Беси есть строка длины \(N\) (\(1\le N\le 3\cdot 10^5\)) состоящая только из символов M и O. Для каждой позиции \(i\) в этой строке есть цена замены (\(1\le c_i\le 10^8\)) этого символа на другой.

Беси думает, что строка будет выглядеть лучше, если она будет содержать больше moo длиной \(L\) (\(1\le L\le \min(N, 3)\)). Moo длиной \(L\) is символ M за которым следуют \(L-1\) символов O.

Для каждого положительного целого \(k\) от \(1\) до \(\lfloor N/L\rfloor\) включительно, вычислите минимальную стоимость изменить строк так, чтобы она содержала как минимум \(k\) подстрок равных moo длины \(L\).

У Беси есть \(N\) (\(1\le N\le 2\cdot 10^5\)) работ для Вас. Если Вы выберете \(i\)-ую работу, её необходимо начать в момент времени \(s_i\) или до него и для её завершения требуется \(t_i\) единиц времени. (\(0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}\)).

Какое максимальное количество работ Вы успеете выполнить? Время начинается с \(0\),и, если Вы начали работу, Вы сначала должны выполнить и только потом начинать другую работу.

\(N\) \((1 \leq N \leq 10^5)\) коров Фермера Джона выстроены в ряд. \(i\)-ая корова имеет метку \(a_i\) (\(1 \leq a_i \leq N\)). Группа коров может сформировать дружескую группу, если все они имеют одну и ту же метку и каждая корова находится в пределах \(x\) коров от остальных коров группы, где \(x\) - целое число из интервала \([1,N]\). Каждая корова должна быть точно в одной дружеской группе.

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

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

Корова Бесси только что закончила курс графовых алгоритмов. И выполнила кодирование своего собственного графического визуализатора! В настоящее время ее визуализатор графов только способен визуализировать корневые деревья с узлами различных значений, и он может выполнять только один вид операции: слияние.

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

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

Учитывая ее начальное и конечное деревья, определите последовательность операций слияния, которые могла бы выполнить Бесси. Гарантируется, что последовательность существует.

Каждый вход состоит из \(T\) (\(1\le T\le 100\)) независимых подтестов. Гарантируется, что сумма \(N\) по всем тестам не превышает \(1000\).

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строку "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiexbessieb» — строка, содержащая два последовательных подстроки, равные "bessie".

Дана строка длиной не более \(2\cdot 10^5\), состоящая только из символов a-z, где каждый символ имеет связанную стоимость удаления, вычислите максимальную количество непрерывных подстрок, равных "bessie", которые вы можете сформировать, удалив ноль или более символов из него, и минимальную общую стоимость символов, которую вам нужно удалить, чтобы сделать это.

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

Чтобы отпраздновать начало весны, \(N\) коров фермера Джона (\(1 \leq N \leq 2 \cdot 10^5\)) придумали новый интригующий танец, в котором они встают в круг и перестраиваются предсказуемыv способом.

В частности, по кругу есть \(N\) позиций, пронумерованные последовательно от \(0\) до \(N-1\), причем позиция \(0\) следует за позицией \(N-1\). На каждой позиции находится корова. Коровы также последовательно нумеруются от \(0\) до \(N-1\). Изначально корова \(i\) находится в позиции \(i\). Вам сообщают набор из \(K\) позиций \(0=A_1<A_2< \ldots< A_K<N\), которые являются «активными», что означает, что коровы в этих позициях будут двигаться следующими (\(1 \leq K \leq N\)).

В каждую минуту танца происходят две вещи. Во-первых, коровы в активных позициях меняются: корова в позиции \(A_1\) перемещается в позицию \(A_2\), корова в позиции \(A_2\) перемещается в позицию \(A_3\) и так далее, с коровой в позиции \(A_K\) переход на позицию \(A_1\). Все эти \(K\) перемещения происходят одновременно, поэтому после завершения вращения все активные позиции по-прежнему содержат ровно одну корову. Далее смещаются сами активные позиции: \(A_1\) становится \(A_1+1\), \(A_2\) становится \(A_2+1\) и так далее (если \(A_i = N-1\) для некоторой активной позиции, то \(A_i\) возвращается к \(0\)).

Рассчитайте порядок коров после \(T\) минут танца (\(1\le T\le 10^9\)).

Фермер Джон заинтересован в лучшем общении со своими собратьями-коровами, поэтому он решил, что он выучит язык мычания!

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

Предложение должно соответствовать одному из следующих форматов:

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

Два предложения можно соединить в сложносочиненное, если поставить союз между ними. Полученное сложносочиненное предложение не может быть далее объединено с другими предложениями или другими сложными предложениями. Каждое предложение (или составное предложение, если два предложения соединены) должно заканчиваться точкой.

У фермера Джона есть банк слов из \(N\) слов, \(C\) запятых и \(P\) точек. (\(1 \leq P,C\le N \leq 10^3\)). Он может использовать слово или знак препинания столько раз раз, сколько это появляется в банке слова. Помогите ему вывести последовательность предложений, содержащую максимально возможное количество слов.

Каждый входной файл содержит \(T\) (\(1\le T\le 100\)) подтестов.

Однако фермер Джон узнает о плане и пытается перехватить их беседу. Таким образом, некоторые буквы \(S\) равны \(F\), что означает, что фермер Джон запутал сообщение и отправитель неизвестен.

Уровень возбуждения незапутанной беседы – это количество повторных отправок коровы, то есть количество вхождений подстроки \(BB\) или \(EE\) в \(S\). Вы хотите найти уровень возбуждения исходного сообщения, но вы не знаете, какие из сообщений фермера Джона на самом деле были сообщениями Бесси. / Элси. По всем возможностям выведите все возможные уровни возбуждения \(S\).

ПР�МЕР ВВОДА:

4
BEEF

ПР�МЕР ВЫВОДА:

2
1
2

ПР�МЕР ВВОДА:

9
FEBFEBFEB

ПР�МЕР ВЫВОДА:

2
2
3

ПР�МЕР ВВОДА:

10
BFFFFFEBFE

ПР�МЕР ВЫВОДА:

3
2
4
6

Авторыы: William Yue and Claire Zhang

В момент времени \(t=0\) Беси расположена в точке \(x=0\) на бесконечной числовой прямой. Она двигается влево или вправо каждую секунду. Однако после \(T\) секунд Беси возвращается в точку \(x=0\).

Фермер Нхой знает сколько раз Беси пересекала точки \(x=.5, 1.5, 2.5, \ldots, (N-1).5\), и это задаётся числами массива \(A_0,A_1,\dots,A_{N-1}\) (\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\), \(\sum A_i\le 10^6\)). Беси никогда не попадает ни в \(x>N\) ни в \(x<0\).

В частности, маршрут Беси может быть представлен строкой символов \(T = \sum_{i=0}^{N-1} A_i\) \(L\) и \(R\), где \(i\)-ый символ представляет направление движения Беси во время \(i\)-ой секунды. Количество изменений направления движения определяется как количество \(LR\) плюс количество \(RL\).

Помогите ФН найти любой маршрут Беси, который соответствует массиву \(A\) и имеет минимальное количество изменений направления движения. Гарантируется существование как минимум одного такого маршрута.

**Замечание: Время на тест в этой задаче 8s, в четыре раза больше чем по умолчанию.**

У Фермера Джона есть большое квадратное поле из \((N+1)\times (N+1)\) (\(1\le N\le 1500\)) ячеек. Пусть ячейка \((i, j)\) обозначает ячейку в \(i\)-ой строке сверху, и в \(j\)-ом столбце слева. В каждой ячейке \((i, j)\) живёт по одной корове (\(1 \le i, j \le N\)), и каждая ячейка содержит указатель или вправо или вниз. Также каждая ячейка \((i, j)\) такая, что \(i=N+1\) или \(j=N+1\), кроме \((N+1, N+1)\), содержит бак с коровьей едой. Каждый чан содержит еду различной цены. Чан в ячейке \((i, j)\) стоит \(c_{i, j}\) (\(1 \le c_{i,j} \le 500\)).

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

Чтобы поддержать свой бюджет, ФД хочет узнать общую стоимость еды съедаемой коровами каждый день. Однако, каждый день перед обедом корова в некоторой ячейке \((i, j)\) меняет направление указателя "вправо" на "вниз" или наоборот. Этот знак остаётся в таком направлении и в последующие дни, пока не будет перевёрнут обратно позже.

Вам даны координаты указателя, который меняется каждый день. Выведите стоимость каждого дня (всего \(Q\) дней, \(1 \le Q \le 1500\)).

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

Формально, у Вас есть дерево с вершинами помеченными \(1\dots N\) (\(2\le N\le 2\cdot 10^5\)) с корнем в вершине \(1\). Каждая вершина изначально не активна. За одну операцию Вы можете переключить одну вершину из неактивного состояния в активное или обратно. Выведите минимально возможную длину последовательности операций, удовлетворяющей обоим нижеуказанным условиям:

• Определим, что поддерево с корнем в вершине \(r\) состоит из всех вершин \(v\) таких, что \(r\) лежит на пути из \(1\) в \(v\) включительно. Для каждого из \(N\) поддеревьев дерева существует момент времени, когда множество активных вершин сосредоточено именно в этом поддереве.
• Каждая вершина неактивна после выполнения всей последовательности операций.

В момент времени \(t=0\), Беси находится в точке \(x=0\) на бесконечной числовой прямой. Она двигается на \(1\) влево или вправо каждую секунду. Ровно через \(T\) секунд она возвращается в точку \(x=0\).

Фермер Нхой знает, сколько раз Беси пересекала точки \(x=.5, 1.5, 2.5, \ldots, (N-1).5\), и это задаётся массивом \(A_0,A_1,\dots,A_{N-1}\) (\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\)). Беси никогда не достигнет ни \(x>N\), ни \(x<0\).

В частности, маршрут Беси может быть представлен строкой \(T = \sum_{i=0}^{N-1} A_i\) символов \(L\) и \(R\), где \(i\)-ый символ представляет направление, в котором двигалась Беси в течение \(i\)-ой секунды. Количество изменений направления определяется как количество пар символов \(LR\) плюс количество пар символов \(RL\) в этой строке.

Помогите ФН посчитать количество маршрутов, соответствующих массиву \(A\) с минимальным количеством изменений направления движения. Гарантируется существование как минимум одного такого маршрута.

Фермер Джон дал Беси \(Q\) строк (\(1 \leq Q \leq 100\)), состоящих только из символов 'M' и 'O.' Любимое слов Беси "MOO", поэтому она хочет преобразовать каждую из этих строк в строку "MOO" используя следующие операции

1. Заменить первый или последний символ на противоположный (то есть, 'M' на 'O', а 'O' на 'M' ).
2. Удалить первый или последний символ.

Для каждой строки определите минимальное количество операций, необходимых чтобы сформировать 'MOO' или выведите '-1', если это невозможно.

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 10^5\)). Каждая корова имеет породу Guernsey или Holstein. Коровы стоят в ряд пронумерованные \(1 \ldots N\).

Каждая корова записала свой список коров. А именно, список коровы \(i\) содержит диапазон коров, начиная с неё самой (коровы \(i\)) и до коровы \(E_i\) (\(i \leq E_i \leq N\)) включительно.

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

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

Очень жаркое лето. Фермер Дон решил купить некоторое количество кондиционеров.

У ФД имеется \(N\) коров (\(1 \leq N \leq 20\)), которые живут в амбаре, содержащем последовательность стойл, пронумерованные \(1 \ldots 100\). Корова \(i\) занимает диапазон стойл, начиная с \(s_i\) и заканчивая в \(t_i\). Диапазоны стойл, занимаемые коровами, не пересекаются. У коров различные требования к охлаждению. Корова \(i\) должна быть охлаждена на количество \(c_i\). Это значает, что для всех стойл, занимаемых коровой \(i\) температура должна быть уменьшена на \(c_i\) единиц.

Амбар содержит \(M\) кондиционеров, помеченных \(1 \ldots M\) (\(1 \leq M \leq 10\)). \(i\)-ый кондиционер стоит \(m_i\) единиц денег, если работает и охлаждает воздух (уменьшает температуру) в стойлах начиная в \(a_i\) и заканчивая в \(b_i\). Если работает, \(i\)-ый кондиционер уменьшает температуру во всех стойлах этого диапазона на величину \(p_i\) (\(1 \leq p_i \leq 10^6\)). Диапазоны стойл кондиционеров могут перекрываться.

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

Имеется \(N\) пастбищ (\(2 \le N \le 2\cdot 10^5\)), соединённых \(N-1\) дорогой, так что ои образуют дерево. Перемещение по каждой дороге занимает одну секунду. В начале на каждом пастбище 0 травы, трава на \(i\)-ом пастбище растёт со скоростью \(a_i\) (\(1\le a_i\le 10^8\)) единиц в секунду. Фермер Джон вначале находится в пастбище 1 и должен удобрить траву на каждом пастбище. Если он посещает пастбище, в котором \(x\) единиц травы, он должен потратить \(x\) единиц удобрений. Удобрять требуется только при первом посещении пастбища и удобрение пастбища занимает 0 единиц времени.

Ввод содержит дополнительный параметр \(T\in \{0,1\}\).

• Если \(T=0\), ФД должен завершить путь в пастбище 1.
• Если \(T=1\), ФД может завершить путь в любом пастбище.

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