Информатика

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

Формально, у Вас есть дерево с вершинами помеченными \(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\) оптимально.

Коровы передают две строки \(s\) и \(t\), каждая с длиной не более \(10^5\), состоящие только из маленьких латинских букв от 'a' до 'r'. Вы должны ответить на \(Q\) запросов (\(1 \leq Q \leq 10^5\)). Для каждого запроса нужно ответить, совпадут ли строки, если в каждой из них оставить только указанные в запросе маленькие латинские буквы (удалив все остальные символы).

1. Выбрать два соседних одинаковых символа и удалить их.

2. Выбрать один символ и заменить его на два других символа в любом порядке.

В задаче требуется дать ответ для \(Q\) (\(1\le Q\le 2\cdot 10^5\)) подстрок строки \(s\).

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

Сколько максимально яблок смогут поймать коровы, если будут действовать сообща оптимально?

У ФД есть коровы двух пород Guernseys и Holsteins. Чтобы сделать свою фотографию как можно более эстетичной, он хочет выстроить своих коров так, чтобы как можно больше коров породы Guernseys находились на позициях с чётными номерами (первая позиция в ряду - нечётная, следующая чётная и т.д.). Для перестройки порядка коров он может только попросить "префикс" своих коров четной длины сделать реверс. "Префикс" состоит из диапазона коров от первой коровы до \(j\)-ой коровы для некоторой позиции \(j\).

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

• Если высоты двух соседних стогов сена различаются не более чем на \(K\) (\(1\le K\le 10^9\)), она может поменять местами два стога

Какую лексикографически минимальную последовательность высот Беси может получить после некоторой последовательности таких операций?

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

Имеется массив отсортированных чисел \(x_1 \leq x_2 \leq \dotsb \leq x_N\) (\(1 \leq N \leq 10^5\)), и целое число \(K\). Вы не знаете массив или \(K\) но Вы знаете для каждого индекса \(i\), наибольший индекс \(j_i\) такой, что \(x_{j_i} \leq x_i + K\). Гарантируется, что \(i\le j_i\) и \(j_1\le j_2\le \cdots \le j_N\le N\).

По заданной информации коровы ФД должны сконструировать любой массив, который соответствует данной информации для некоторого целого \(K\). Конструкция должна удовлетворять условию \(0 \leq x_i \leq 10^{18}\) для всех \(i\) и \(1 \leq K \leq 10^{18}\).

Можно доказать, что это всегда возможно. Помогите коровам ФД решить эту задачу.

SCORING:

• Для 50% всех тестов, \(N\le 5000\)
• Для оставшихся тестов нет дополнительных ограничений.