Информатика

Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов \(1\) и \(2\), которые плохо смешиваются одна с другой. У неё также есть две различных колбы бесконечной емкости наполненные \(N\) \((1 \leq N \leq 10^5)\) единицами смесей жидкостей этих двух цветов. Смеси делятся на слои отдельных цветов. Поэтому колбы можно рассматривать как строки \(f_1f_2\ldots f_N\) и \(s_1s_2\ldots s_N\) где \(f_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна первой колбы, \(s_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна второй колбы,

Беси хочет разделить эти жидкости так, чтобы каждая колба содержала все единицы жидкости одного цвета. У Беси есть также пустой стакан бесконечной емкости, чтобы помочь ей решить её задачу. Когда Беси делает одно переливание, она переливает всю жидкость цвета \(i\) наверх из одной колбы в другую или в стакан.

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

В каждом тесте будет \(T\) (\(1 \leq T \leq 10\)) подтестов с параметром \(P\) для каждого подтеста.

Предположим, что минимальное количество переливаний, чтобы разделить жидкости по колбам равно \(M\).

• если \(P=1\), Р’С‹ получите баллы, если выведите только \(M\).
• Если \(P=2\), Р’С‹ получите баллы, если выведите целое число \(A\) такое, что \(M \leq A \leq M+5\), Р·Р° которым следует \(A\) строк, которые конструируют это решение Р·Р° \(A\) С…РѕРґРѕРІ. Каждая строка должна содержать описание источника Рё приемника жидкости (\(1\), \(2\), или \(3\) для стакана). Колба-источник должна быть непустой перед переливанием, Рё нельзя переливать РІ себя.
• If \(P=3\), Р’С‹ получите баллы, если выведите \(M\), Р·Р° которым следует правильная конструкция, использующая это количество С…РѕРґРѕРІ.

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

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

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

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

Вот как это делается

1: 1221
2: 2211
3: 

1: 122
2: 22111
3: 

1: 1
2: 22111
3: 22

1: 1111
2: 22
3: 22

1: 1111
2: 2222
3:

В последнем подтесте пминимальное количество переливаний - \(5\). Однако, поскольку \(P=2\), то данная конструкция с \(6\)-ю ходами корректна, посокльку она не более чем на \(5\) переливаний от оптимального ответа.

Автор: Suhas Nagar

Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить никакие тесты для экономии энергии или потратить \(3^{a-1}\) энергии для подготовки \(a\) тестов для некоторого положительного целого \(a\).

У Фермера Джона есть \(D\) (\(1\le D\le 2\cdot 10^5\)) требований. Для \(i\)-го требования он говорит Беси, что в течение первых \(m_i\) минут она должна приготовить не менее чем \(b_i\) тестов (\(1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}\)).

Пусть \(e_i\) - минимальное количество энергии, которое необходимо Беси, чтобы удовлетворить первые \(i\) требований. Выведите \(e_1,\dots,e_D\) по модулю \(10^9+7\).

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\)) городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\). являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе \(c_{i, t\bmod{T_i}}\).

У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия, каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\) раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

\(N\) \((1 \leq N \leq 5 \cdot 10^5)\) коров Фермера Джона выстроены в круг. \(i\)-ая корова имеет ведро с целой вместимостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально полные.

Каждую минуту корова \(i\) передаёт всё молоко из своего ведра корове \(i+1\) для \(1\le i<N\), а корова \(N\) передаёт своё молоко корове \(1\). Все обмены проходят одновременно (то есть, если корова отдаёт \(x\) литров молока и также получает \(x\) литров молока, её количество молока не изменяется). Если количество молока у коровы \(i\) превысит значение \(a_i\), тогда лишнее молоко теряется.

После каждой из минут \(1, 2, \dots, N\) - сколько молока останется у всех коров вместе?

\(N\) \((1 \leq N \leq 2 \cdot 10^5)\) коров Фермера Джона выстроены в круг так, что для каждой коровы \(i\) в промежутке \(1,2,\dots,N-1\), справа от коровы \(i\) расположена корова \(i+1\), а справа от коровы \(N\) находится корова \(1\). У каждой коровы имеется ведро целочисленной ёмкостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально заполнены молоком.

Каждую минуту коровы обменивается молоком по правилу, описанному в строке \(s_1s_2\dots s_N\) , состоящей только из символов \(\text{�L’}\) и \(\text{�R’}\). Если у коровы есть хотя бы \(1\) литр молока, она отдаст ровно \(1\) литр молока корове слева от неё, если \(s_i=\text{�L’}\), или справа от неё, если \(s_i=\text{�R’}\). Все обмены происходят одновременно (то есть, если у коровы полное ведро и она отдаёт литр молока и получает литр молока, то её молоко сохраняется). Если количество молока превысит \(a_i\), то лишнее молоко будет утеряно.

ФД хочет узнать после \(M\) минут \((1 \leq M \leq 10^9\)), какое количество молока останется у всех коров.?

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

3 1
RRL
1 1 1

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

2

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

5 20
LLLLL
3 3 2 3 3

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

14

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

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

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

38

Авторы: Chongtian Ma, Alex Liang

У Фермера Джона есть \(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\), посчитайте минимальное количество дружеских групп, которые могу быть сформированы.

Беси вернулась в школу. Она начала делать домашнюю работу по математике, в которой требуется округлить положительные целые числа до степени \(10\).

Чтобы округлить положительное целое число \(a\) к ближайшему \(10^b\), где \(b\) положительное целое число, Беси сначала находит \(b\)-ую цифру справа. Пусть \(x\) обозначает эту цифру.

Если \(x \geq 5\), Беси добавляет \(10^b\) к \(a\).

Затем Беси устанавливает в \(0\) все цифры вправо от \(b\)-ой цифры.

Например, если Беси хочет округлить \(456\) к ближайшей \(10^2\) (сотне), Беси сначала находит 2-ую цифру справа - это \(5\). То есть, \(x = 5\). Затем, поскольку \(x \geq 5\), Беси прибавляет \(100\) к \(a\). Наконец Беси устанавливает в \(0\) все цифры справа начиная со второй, получается \(500\).

Однако если Беси станет округлять \(446\) до ближайшей \(10^2\), она получит \(400\).

Посмотрев на домашнюю работу Беси, Эльза придумала новый тип округления: цепочечное округления. Чтобы цепочечно округлить до ближайшего \(10^b\), Эльза сначала округляет до ближайшего \(10^1\), затем до ближайшего \(10^2\), и т.д. до ближайшего \(10^b\).

Беси думает, что Эльза ошибается, но она сильно занята со своей домашней работой, чтобы подтвердить свои подозрения. Она просит Вас посчитать сколько целых чисел \(x\), начиная с \(2\) и до \(N\) (\(1 \leq N \leq 10^{9}\)) таких, что округление его до ближайшего \(10^P\) отличается от цепочечного округления к ближайшему \(10^P\), где \(P\) - минимальное целое такое, что \(10^P \geq x\).

**Примечание. Ограничение по времени для этой задачи составляет 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\)).