Алгоритмы поиска

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

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

Формат входных данных

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

Формат выходных данных

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. \(i\)-ый этаж требует выполнения \(a_i\) единиц работы , каждая корова завершает одну единицу работы ровно за час. Поэтому если \(c\) коров работают на этаже \(i\), то они выполнят всю работу ровно за \(a_i / c\) единиц времени. Из соображений безопасности, этаж \(i\) должен быть завершён прежде чем начнётся работа на этаже \(i+1\).

Вычислите минимальное количество времени, за которое может быть построен амбар, если коровы будут распределены по этажам оптимальным способом. Выведите это число округлённым к ближайшему целому. Гарантируется, что решение будет более чем на 0.1 от границы между двумя целыми числами.

Имеется \(N\) стогов сена расположенных в целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\) в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги сена в диапазоне \(x-R \ldots x+R\).

Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\). Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\) коров разрушить все стоги сена на сцене.

Имеется \(N\) стогов сена, расположенных в различных целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлится с энергией \(R\) в позиции \(x\), это вызовет взрыв "радиусом \(R\)", что вызовет взрывы всех стогов сена в диапазоне \(x-R \ldots x+R\). Все стоги сена в этом диапазоне также одновременно взрываются с радиусом взрыва \(R-1\). Все ещё не взорванные стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва \(R-2\), и т.д.

Пожалуйста, определите минимальное количество энергии \(R\), с которым должна приземлиться корова, так что если она приземлится в оптимальном положении, то взорвутся все стоги сена на сцене.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до \(\sqrt{X}\). То есть, квадрат расстояния между коровами стоит не более \(X\) чтобы обеспечить их коммуникацией.

Помогите коровам определить минимальное целое \(X\) такое, что сообщение от любой коровы сможет достичь любой другой коровы.

ФД собирается делать так. Он выбирает положительное целое число \(X\). А затем повторяет следующую процедуру каждый день:

1. Предположим, что ФД уже отдал Беси \(G\) галлонов молока, он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
2. Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
3. Даёт Беси \(Y\) галлонов молока.

Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).

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

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

Например, предположим, что последовательность ящиков вдоль дороги есть 'ABCDABC'. ФД не может выбрать \(K=3\), поскольку если он увидит 'ABC', то имеется два расположения такой строки вдоль дороги. Минимальное значение \(K\), которое работает, \(K=4\), поскольку любые последовательные 4 символа уникально определяют его позицию вдоль дороги.

ФД сделал \(M\) наблюдений об этой структуре (\(1 \leq M \leq 50,000\)). Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение \(X\) так, чтобы выполнились условия первых \(X\) наблюдений. Если несколько порядков дойки могут удовлетворять \(X\) наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок \(x\) является лексикографически меньшим, чем порядок \(y\), если для некоторого \(j\), , \(x_i = y_i\) для всех \(i < j\) и \(x_j < y_j\) (другими словами два порядка идентичны до некоторой точки, в которой \(x\) меньше чем \(y\)).

Помогите ФД определить наилучший порядок дойки его коров.

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно \(N\) (\(1 \leq N \leq 10^5\)) коров прибывают в аэропорт, и корова \(i\) прибывает в момент времени \(t_i\) (\(0 \leq t_i \leq 10^9\)). ФД организовал \(M\) (\(1 \leq M \leq 10^5\)) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до \(C\) (\(1 \leq C \leq N\)) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что \(MC \geq N\).

Еда будет представлять собой непрерывный интервал, содержащий один или более последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).

Она не будет включать в размещение два алмаза, если их размеры отличаются более чем на \(K\). По данному \(K\) определите максимальное количество алмазов, которые Беси разместит в амбаре.