Информатика

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

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

Дана строка \(s\), пусть \(B(s)\) представляет собой максимальное количество повторяющихся копий. из «bessie» можно получить, удалив ноль или более символов из \(s\). В приведенном выше примере \(B(\)"bqessiyexbesszieb"\() = 2\). Кроме того, учитывая строка \(t\), пусть \(A(t)\) представляет собой сумму \(B(s)\) по всем непрерывным подстроки \(s\) строки \(t\).

У фермера Джона есть строка \(t\) длины не более \(2\cdot 10^5\), состоящая только из символов a-z. Пожалуйста, рассчитайте \(A(t)\) и как \(A(t)\) изменится после \(U\) (\(1\le U\le 2\cdot 10^5\)) обновлений, каждое из которых изменяет символ \(t\). Обновления являются кумулятивными.

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

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

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

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

Каждый вход состоит из \(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\) с минимальным количеством изменений направления движения. Гарантируется существование как минимум одного такого маршрута.

Беси работает в текстовом редакторе miV! Его функция "найти и заменить" позволяет ей заменить все вхождения маленькой латинской буквы \(c\) на непустую строку из маленьких латинских букв \(s\). Например, дана строка "\(\texttt{ball}\)". Если Беси выберет в качестве \(c\) символ 'l' а в качестве строки \(s\) "\(\texttt{na}\)", данная строка трансформируется в "\(\texttt{banana}\)".

Беси начинает со строки "\(\texttt{a}\)" и трансформирует её используя некоторое количество операций «найти и заменить» и получает финальную строку \(S\). Поскольку \(S\) может быть большой, она хочет узнать по заданным \(l\) и \(r\) \(1\le l\le r\le \min(|S|,10^{18})\), чему равно \(S_{l\dots r}\) - подстрока S с позиции \(l\) по позицию \(r\) включительно.

Гарантируется, что сумма \(|s|\) по всем операциям не более \(2\cdot 10^5\), и что \(r-l+1\le 2\cdot 10^5\).

Фермер Джон дал Беси \(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\), ФД может завершить путь в любом пастбище.

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

Беси любит смотреть шоу на сервисе Mooloo. Поскольку Беси очень занятая корова, она создаёт план на следующие \(N\) (\(1 \leq N \leq 10^5\)) дней в течение которых будет смотреть шоу. Mooloo - платный сервис и она хочет минимизировать оплату.

У Mooloo интересная система подписки: она стоит \(d + K\) денег (\(1\le K\le 10^9\)), чтобы подписаться на \(d\) последовательных дней. Вы можете начать подписку в любой день. И Вы можете начать новую подписку, если текущая подписка истекла. Определите минимальное количество денег, чтобы заплатить за просмотр шоу.

Беси - голодная корова. Каждый день на обед если есть пакеты сена в амбаре, она съедает ровно один пакет. Чтобы Беси не голодала, Фермер Джон присылает в некоторые дни некоторое количество пакетов с сеном, которые прибывают утром (до обеда). В частности в день \(d_i\), ФД присылает \(b_i\) пакетов сена (\(1\leq d_i \leq 10^{14}\), \(1 \leq b_i \leq 10^9\)).

Вычислите общее количество пакетов сена, которые съест Беси в течение \(T\) дней.

Беси - робокорова, также известная как корборг. Она на числовой прямой старается выстрелить по \(T\) \((1 \leq T \leq 10^5)\) целям, расположенным в различных позициях. Беси начинает в позиции \(0\) и и следует строке из \(C\) \((1 \leq C \leq 10^5)\) команд, каждая из которых одна из букв L, F, или R:

• L: Беси двигается на одну единицу влево.
• R: Беси двигается на одну единицу вправо.
• F: Беси стреляет. Если в текущей позиции Беси находится цель, она разрушается и её больше нельзя разрушить.

Если Вам разрешено изменить не более одной команды в строке на другую команду, прежде чем Беси начнёт следовать этой строке команд, какое максимальное количество целей сможет поразить Беси?

Фермер Джон решил потренировать своих коров в акробатике. Сначала он взвесил своих коров и определил, что они имеют \(N\) (\(1\le N\le 2\cdot 10^5\)) различных весов. В частности, для каждой \(i\in [1,N]\), \(a_i\) из его коров имеют вес \(w_i\) (\(1\le a_i\le 10^9, 1\le w_i\le 10^9\)).

Его наиболее популярный трюк включает коров, формирующих сбалансированную башню. Башня это последовательность коров, стоящих одна на другой. Башня называется сбалансированной, если каждая корова с коровой над ней имеет вес не менее чем на (\(1\le K\le 10^9\)) больший, чем вес коровы непосредственно над ней. Каждая корова может быть частью не более чем одной сбалансированной башни.

Если ФД хочет создать не более \(M\) (\(1 \le M \le 10^9\)) сбалансированных башен из своих коров, какое наибольшее количество коров может быть частью некоторой башни?

Фермер Джон развозит сено по ферме.

Ферма имеет \(N\) \((1\le N\le 2\cdot 10^5)\) амбаров, расположенных в целых точках \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) на числовой прямой. ФД запланировал \(N\) перевозок сена в некоторую целую точку \(y\) \((0 \le y \le 10^6)\) и затем одну перевозку к каждому амбару.

К несчастью служба доставки очень расточительна. В частности, для некоторых \(a_i\) и \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) пакетов сена теряются на единицу расстояния каждой доставки влево и \(b_i\) пакетов сена теряются на единицу расстояния каждой доставки вправо. Формально при транспортировке из точки \(y\) в амбар в точке \(x\), количество теряемых пакетов сена определяется как

Вам даны \(Q\) \((1\le Q\le 2\cdot 10^5)\) независимых запросов, каждый состоит из возможных значений \((a_i,b_i)\), помогите ФД определить наименьшее количество потерянных пакетов сена, если он выберет \(y\) оптимально.