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

\(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона выстроены в ряд так, что \(i\)-ая корова в этому ряду имеет уровень голода \(h_i\) (\(0 \leq h_i \leq 10^9\)). Поскольку коровы - социальные животные и хотят есть вместе, единственный способ уменьшить уровень голода его коров - выбрать двух соседних коров с номерами \(i\) и \(i+1\) и скормить каждой из них по мешку кукурузы, чтобы уменьшить уровень голода каждой из них на один.

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

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

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

ФД это заметил и попросил Эльзу вести учёт засыпаний Беси. Всего имеется \(N\) (\(1\le N\le 10^5\)) периодов, когда проходили занятия. И Эльза записала, что Беси засыпала \(a_i\) (\(0\le a_i\le 10^6\)) раз во время \(i\)-го периода. Общее количество засыпаний Беси не превышает \(10^6\).

Эльза хочет показать ФД, что Беси всегда засыпала одинаковое количество раз. Но единственный способ, которым она это может сделать - объединить два соседних периода проведения занятий. Например, если \(a=[1,2,3,4,5],\) то Эльза может объединить второй и третий периоды и лог станет таким \([1,5,4,5]\).

Помогите Эльзе вычислить минимальное количество модификаций лога, которые она должна сделать, чтобы сделать все числа лога равными.

Изначально коровы выстроились в порядке \(a_1,a_2,\ldots,a_N\) слева направо. Цель ФД выстроить их в порядке \(b_1,\ldots,b_N\) слева направо. Чтобы достичь своей цели, ФД может выполнить несколько модификаций порядка. Каждая модификация состоит в том, чтобы выбрать корову и переместить её влево на некоторое количество позиций.

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

У Беси \(N\) (\(1 \le N \le 2000\)) друзей. Однако они разные! Друг \(i\) имеет счёт популярности \(P_i\) (\(1 \le P_i \le 2000\)), и Беси хочет максимизировать сумму популярности друзей, которые пойдут с ней. Друг \(i\) пойдёт с ней только если она даст ему \(C_i\) (\(1 \le C_i \le 2000\)) "moonies". Друг \(i\) также может сделать скидку в \(1\) "mooney", если она даст ему \(X_i\) (\(1 \le X_i \le 2000\)) мороженых. Беси может получить сколько угодно скидок.

У Беси есть \(A\) moonies и \(B\) мороженых (\(0 \le A, B \le 2000\)). Помогите ей определить максимальную сумму популярностей, которую она может добиться, если потратит mooney и мороженое оптмально.

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

Каждая корова готова пройти не более \(K\) (\(0 \le {K} \le N-1\)) позиций чтобы добраться до пакета с травой. Определите минимальное количество пакетов с травой, необходимое чтобы накормить всех коров. Любая конфигурация, удовлетворяющая указанным выше ограничениям, будет рассматриваться как корректная.

Коротая время, Милдред бормочет cowphabet опять и опять. Фермер Нхой хочет узнать, сколько раз она пробормотала cowphabet.

По заданной строке букв, которые услышал ФН, вычислите минимальное количество раз, которое Милдред пробормотала весь cowphabet. ФН мог не услышать некоторые из букв, которые бормотала Милдред.

Замечание: время на тест для этой задачи удвоено.

ФД хочет выбрать \(N\) (\(1\le N\le 2\cdot 10^5\)) (не обязательно в целых числах) для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН, но они могут находится в позициях травяных пастбищ.

Корова какого фермера находится ближе к травяному пастбищу, тот и объявляется собственником этого пастбища. Если коровы обоих фремеров находятся на одинаковом расстоянии от пастбища, то оно объявляется принадлежащим ФН.

По заданным позициям коров ФН и вкусностям пастбищ определите максимальную вкусность суммарную, которой может добиться ФД оптимальным размещением своих коров.

Эти коровы сейчас стоят в ряд и ФД хочет сделать фото каждой последовательности из трёх или более последовательных коров. Однако он не хочет делать фото, в котором ровно одна корова породы Guernsey или ровно одна корова породы Holstein --- он считает, что эта одна корова будет чувствовать себя изолированной. После взятия фото каждой последовательности из трёх или более коров, он выбрасывает так называемые "одинокие" фото, на которых ровно одна корова породы Guernsey или ровно одна корова породы Holstein.

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

Амабар Фермера Джона содержит последовательность из \(N\) стойл, пронумерованных \(1 \ldots N\), каждое содержит ровно одну корову. \(i\)-ая корова предпочитает, чтобы температура в её стойле была \(p_i\), а прямо сейчас температура в её стойле \(t_i\). Для того чтобы угодить всем коровам, ФД установил новую систему кондиционирования, которая работает следующим образом. ФД посылает команды системе - увеличить или уменьшить температуру в некоторых подряд идущих стойлах на 1 (например, увеличить на 1 температуру в стойлах \(5 \ldots 8\)). Последовательность стойл может состоять из одного стойла.

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

Беси хочет максимизировать количество ягод, которое она соберёт. Однако ФД хочет, чтоб Беси поделилась ягодами со своей младшей сестрой, поэтому Беси должна отдать Эльзе \(K/2\) корзин с наибольшим количеством ягод. Это значит, что у Эльзы может даже оказаться больше ягод чем у Беси.

Помогите Беси вычислить максимальное количество ягод, которое она может получить после делёжки.

Беси всегда бежит к финишу и хочет финишировать после целого количества секунд. Кроме того, она не хочет прибежать слишком быстро, поэтому на финише её скорость не может превысить \(X\) (\(1 \leq X \leq 10^5\)) метров в секунду. Беси хочет узнать, как быстро она сможет закончить гонку для \(N\) (\(1 \leq N \leq 1000\)) различных величин \(X\).

Определите объединение отрезов, которое будет множеством всех \(x\) которые содержатся внутри хотя бы одного отрезка. также определите сложность множества отрезков как количество связанных отрезков, представленных в этом объединении.

Беси хочет вычислить сумму сложностей во всем \(2^N\) подмножествам заданного множества из \(N\) отрезков по модулю \(10^9+7\).

Помогите Беси!

Фермер Джон остановился около игры и хочет узнать минимальное количество обменов между соседними элементами, которые нужно совершить, чтобы игра получила ничейный счёт. ФОРМАТ ВВОДА (файл balance.in): Первая строка ввода содержит \(N\), следующая строка содержит \(2N\) целых чисел каждое из которых равно 0 или 1. ФОРМАТ ВЫВОДА (файл balance.out): Выведите количество соседних обменов, которые нужно сделать, чтобы игра получила ничейный счёт.

В настоящий момент коровы выстроились в линию в порядке \(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\). Он хочет переупорядочить коров так, чтобы они стали в порядке \(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.

Фермера Джона слышит только корова, которая стоит перед ним. В этот момент ФД может сказать ей перейти на \(k\) позиций назад (\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит, двигаются вперёд, освобождая место для неё, в которое она и становится.

Например, пусть \(N=4\) и коровы стоят в таком порядке

 ФД: 4, 3, 2, 1 

Единственная корова, которая слышит ФД, это корова \(4\). Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:

 ФД: 3, 2, 4, 1 

Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.

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

Главное поле фермы представлено прямой, на которой каждая корова занимает некоторое положение в целочисленной координате. Изначально все \(N\) коров находятся в различных позициях. ФД хочет, чтобы они заняли соседние позиции (например 3,4,5,6,7,8).

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

Определите минимальное и максимальное количество таких перемещений, чтобы коровы заняли \(N\) последовательных позиций.

Беси решила воспользоваться им для поиска партнёра. Он создала аккаунт и получила список из \(N\) возможных соответствий (\(1\leq N \leq 10^6\)). Беси оценила, что каждый бык имеет вероятность \(p_i\) (\(0<p_i<1\)) согласиться на её приглашение на танец.

Беси решила послать приглашение каждому быку в некотором непрерывном интервале списка, но так, чтобы получить ровно одного партнёра. Помогите Беси определить максимальную вероятность получить ровно одно принятое приглашение, выбрав правильный интервал.

В сарае ФД есть четыре ведра, каждое хранит семена своего типа. ФД хочет посадить на каждом пастбище траву семенами одного из этих типов. ФД хочет каждой их своей коров различную диету. Каждая из его \(M\) коров имеет два любимых пастбища. И он хочет гарантировать, чтобы на каждой такой паре пастбищ была засеяна трава различных типов, и тогда каждая корова сможет выбирать из двух видов травы. ФД знает, что нет пастбища, которое нравится более чем трём коровам.

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

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

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

Определите минимальное и максимальное количество перемещений, которое возможно сделать прежде чем коровы расположатся в трёх последовательных позициях.

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