Жадный алгоритм

У Фермера Джона \(N\) (\(1\le N\le 2\cdot 10^5\)) участков травы на прямой, где участок \(i\) имеет уровень бактерий, который отличается на \(a_i\) от здоровой травы (\(-10^{15}\le a_i \le 10^{15}\)). Например, если \(a_i = -3\), тогда кусок \(i\) имеет уровень бактерий на 3 меньше, чем нормальный. И нужно прибавить ровно 3 дополнительных единицы бактерий, чтобы уровень бактерий в этом куске рассматривался как нормальный.

ФД хочет обеспечить, чтобы каждый кусок травы был скорректирован, чтобы получить нормальные уровни бактерий на них. У него есть два вида пестицидов, один добавляет бактерии, другой удаляет бактерии. ФД распространяет любой из двух видов пестицидов, стоя в куске \(N\) (самом правом куске) и выбирает уровень мощности \(L\) (\(1 \leq L \leq N\)).

Сила действия спрейера уменьшается по мере увеличения расстояния от него. Например, если фермер выберет пестицид, который добавляет бактерии, тогда \(L\) единиц бактерий в участок \(N\), \(L-1\) единиц бактерий в участок \(N-1\), \(L-2\) единицы бактерий в участок \(N-2\) и т.д. Участки \(1 \ldots N-L\) не получат бактерий, поскольку мощность спрейера недостаточна, чтобы их достать. Аналогично, если ФД выберет пестициды, которые удаляют бактерии, тогда \(L\) единиц бактерий будет удалено с участка \(N\), \(L-1\) единиц бактерий будет удалено с участка \(N-1\) и т.д. Опять, участки \(1 \ldots N-L\) будут не изменены.

Определите минимальное количество раз, которое ФД должен применить свой спрейер так, чтобы на каждом участке стало рекомендованное количество бактерийю Гарантируется, что ответ не превысит \(10^9\).

Может потребоваться использование 64-битного типа данных (например "long long" в C/C++)

Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов \(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

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить никакие тесты для экономии энергии или потратить \(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\).

\(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 \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

**Замечание: Время на тест для этой задачи 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\),и, если Вы начали работу, Вы сначала должны выполнить и только потом начинать другую работу.

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

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

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

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

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

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

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

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

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

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

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

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

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

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции \(A\) и \(B\). В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени \(t\), тогда он прибудет на другую станцию в момент времени \(t+T\) (\(1\le T\le 10^{12}\)).

Имеется \(N\) (\(1\le N\le 5000\)) поездов для которых нужно установить время отправки. \(i\)-ый поезд должен покинуть станцию \(s_i\) в момент времени $t_i или позже (\(s_i\in \{A, B\}, 0\le t_i\le 10^{12}\)). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени \(a_i\ge t_i\), общая задержка определяется как \(\sum_{i=1}^N(a_i-t_i)\).

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

ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые растения были выше чем другие. Он дал Вам массив различных целых чисел \(t_1,\dots,t_N\), содержащих все целые числа от \(0\) до \(N-1\) и хочет, чтобы \(i\)-ое растение имело ровно \(t_i\) растений, которые выше этого. Определите минимальное количество дней, чтобы требование ФД было удовлетворено или укажите, что это невозможно.

Заметим, что тесты этой задачи могут потребовать использования 64-битного целого типа (например, "long long" в C/C++).

Фермер Джон выстроил в ряд свои \(N\) коров (\(1 \leq N \leq 3\cdot 10^5\)). К несчастью, стала распространяться болезнь.

Изначально некоторые коровы инфицированы. Каждую ночь инфицированная корова распространяет болезнь на коров соседних слева и справа, если они есть. Однажды инфицированная корова остаётся инфицированной.

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

Коровы Фермера Джона любят конфетные трости. У ФД \(N\) коров с определённой начальной высотой. Он хочет скормить им \(M\) конфетных тростей, различной высоты (\(1\le N,M\le 2\cdot 10^5\)).

ФД планирует кормить коров конфетными тростями одну за одной в порядке, в котором они заданы на вводе. Чтобы кормить коров ФД вывешивает конфетные трости так, чтобы изначально они касались земли. Коровы выстраиваются одна за одной в порядке, как они заданы на входе. Каждая ест до своей высоты (потому что выше не достаёт). Трость остаётся на месте где она изначально была подвешена и не опускается к земле, даже после того как её нижняя часть съедена. Возможно, что когда подойдёт очередь некоторой коровы она ничего не сможет съест, если нижняя часть трости уже выше высоты этой коровы. После того как пройдёт очередь всех коров, они подрастают на высоту равную количеству единиц трости, которую съела корова, а ФД вывешивает новую конфетную трость и коровы повторяют процесс опять (корова 1 всегда начинает есть первой).

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

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

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

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

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