Алгоритмы

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

ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t₁, t₂, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.

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

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

Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t₁, t₂, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.

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

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

Фермер Джон придумал игру для своих коров.

Она играется на решётке R*C (2 <= R <= 15, 2 <= C <= 15), где каждый квадрат раскрашем красным либо синим цветом. Коровы начинают в левом верхнем углу и двигаются в правый нижний последовательными прыжками. Прыжок является корректным если и только если:

1) Вы прыгаете на квадрат другого цвета

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

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

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

Первая строка содержит два целых числа R и C. Каждая из следующих R строк содержит ровно C символов. Каждый символ или R или B (обозначающих соответтсвенно красный или синий квадрат)

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

Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний.

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

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

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

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

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

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

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

Беси стоит перед огромным камнем в середине своего любимого поля. На камне - шифровка на древнем языке, алфавит которого состоит только из трёх букв C, O, W. Беси интересно, сколько раз встретилось слово COW в тексте.

Бесси не возражает если другие букв встречаются между C O W. Также Беси считает разными слова, в которых отличается хоть одна буква. Например COW встречается только один раз в слове CWOW, два раза в слове CCOW, и 8 раз в слове CCOOWW.

По заданному тексту шифровки помогите Беси посчитать сколько раз появится слово COW.

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

Первая строка ввода содержит одно целое число N <= 10^5. Вторая строка содержит строку из N символов, каждый их которых либо C, либо O, либо W.

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

Выведите количество раз, которое COW появляется как подпоследовательность, необязательно непрерывная, во входной строке.

Заметим, что ответ может быть очень большим, поэтому нужно из пользовать 64-битную целую величину (long long в С++ или long в Java).

Пусть дана строка \(s\), назовём \(F(s)\) строку \(s\) за которой идёт строка \(s\) "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке \(s\), коровы строят свою строку бесконечной длины повторя применение \(F\); каждый шаг удваивает длину текущей строки.

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

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

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

Напомним, подпоследовательность это подмножество \(a(i_1), a(i_2), \ldots, a(i_k)\) элементов из последовательности, где индексы \(i_1 < i_2 < \ldots < i_k\). Мы говорим, что подпоследовательность возрастающая, если \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).

ФД может переупорядочивать коров следующим образом выбрать любую подпоследжовательность и реверсировать её элементы

Например, если мы имееем список

1 6 2 3 4 3 5 3 4

мы можем реверсировать следующие элементы

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

получим

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

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

Определите максимально возможную длину возрастающей подпоследовательности основываясь на факте, что Вы можете реверсировать любую подпоследовательность, но только один раз.

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

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

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом много раз подряд. В действительности, она хочет переключаться между жестами не более чем \(K\) (\(0 \leq K \leq 20\)) раз за все игры. Например, если \(K=2\), она может играть "копыто" первые игры, затем переключиться на бумагу и в конце играть снова "копыто".

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

Амбар описывается решёткой \(N \times N\) (\(2 \leq N \leq 20\)) символов, некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу (1,1) и должна пройти в правый верхний угол \(N,N\). Вы можете управлять ею посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов", "повернись вправо на 90 градусов". Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели. Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей инструкции.

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

ФОРМАТ ВВОДА:

3
EHE
EEE
EEE

ФОРМАТ ВЫВОДА:

9

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.

Problem credits: Brian Dean

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

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

ФД назначил жестам цифры 1 2 3. Помогите ФД определить максимально возможное количество игр, в которых выиграет первая корова, при подходящем назначении цифр жестам.

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

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

Заметим, что применение машины в однмо и том же прямоугольнке дважды бесполезно, поскольку не изменит состояние коров в этом прямоугольнике.

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

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

Фермер Джон начинает в позиции (\(f_x, f_y\)) и планирует сделать \(N\) шагов, каждый из которых в одном из 4 направлений: 'N' (север), 'E' (восток), 'S'(юг), 'W' запад. Беси начинает в позиции (\(b_x, b_y\)) и делает аналогичные \(M\) шагов. Эти пути могут иметь общие точки. В каждый момент времени ФД может остаться в своей текущей позиции либо сделать один шаг вперёд по своему маршруту (если ещё не достиг финальной позиции). В каждый момент времени (исключая тот момент, когда они находятся в стартовой позиции), энергия, потреблённая их радиоустройствами равна квадрату расстояния между ними.

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

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

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

Ферма представлена двумерной решёткой квадратных ячеек. AL начинает одной из этих ячеек в момент времени \(t = 0\), косит траву в этой ячейке. Поэтому изначально трава выкошена только в этой ячейке. Дальнейшие действия ФД описываются последовательностью из \(N\) предложений. Например, если первое предложение "W 10" то для моментов времени от \(t = 1\) до \(t = 10\) (то есть, следующие 10 единиц времени), ФД будет продвигаться по 1 ячейке на запад, кося траву в каждой ячейке по пути.

ФД медленно косит траву настолько, что она может успеть вырасти ещё прежде чем он закончит процесс. Любая ячейка травы, которую выкосили в момент времени \(t\) вырастет снова в момент времени \(t + x\).

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

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

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

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