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

У Беси \(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).

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

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

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

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

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

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(10^9\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

К несчастью, ФД нанял на \(K\) спасателей больше чем может платить зарплату. При условии, что он должен уволить ровно \(K\) спасателей, какой максимальный интервал времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если присутствует хоть один спасатель в это время.

Но в тот момент, когда Беси приземляется, закон сможет определить ее местоположение. Некоторые фермеры начнут в различных выходных амбарах и попытаются поймать Беси. Фермеры двигаются на той же скорости, что и Беси (поэтому в каждый момент времени каждый фермер может перейти из своего амбара в соседний). Фермеры всё время знают, где находится Беси, и Беси всё время знает, где находятся фермеры. Фермеры поймают Беси, если в некоторый момент времени, один из фермеров находится в том же амбаре, что и Беси или проходит по тому же туннелю, что и Беси. Беси сбежит, если достигнет амбара с выходом, прежде чем любой из фермеров поймает её.

Беси не уверена в своих шансах на успех, которые зависят от количества фермеров, которые будут за ней охотиться. Для каждого из \(N\) амбаров, в которых может приземлиться Беси, определите минимальное количество фермеров, которое необходимо, чтобы поймать Беси, в предположении, что фермеры распределяться оптимально среди выходных амбаров.

Заметим время на тест в этой задаче больше чем по умолчанию: 4 секунды для C/C++/Pascal, и 8 секунд для Java/Python.

Фермер Джон начинает с фрагмента \(1\) и должен достичь фрагмента \(N\), чтобы разбудить своих коров. Фрагмент \(1\) защищён крышей фермы, а фрагмент \(N\) - крышей амбара, поэтому на них нет снега. Но чтобы ходить по другим фрагментам ФД должен носить ботинки.

У ФД есть \(B\) пар ботинок, пронумерованных \(1 \dots B\). Некоторые из них тяжёлые, а некоторые полегче. В частности, пара \(i\) позволяет ФД ходить по снегу не более \(s_i\) футов глубины и позволяет ФД продвигаться на расстояние \(d_i\) вперёд на каждом шагу.

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

ФД может менять ботинки только когда стоит на фрагменте. Если он стоит на фрагменте, то и те ботинки, которые он снимает, и те ботинки, которые он надевает, должны быть выше снега, как минимум на \(f\) футов. Промежуточные пары ботинок, которые он снимает из стопки ботинок не одевая, могут не удовлетворять этому ограничению.

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