Алгоритмы

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

Поле представляет собой прямоугольник с угловыми вершинами в точках \((0,0)\) and \((A,B)\). ФД построил \(n\) вертикальных изгородей (\(0 \leq n \leq 25,000\)) в различных позициях \(a_1 \ldots a_n\) (\(0 < a_i < A\)); каждая изгородь проходит от точки \((a_i, 0)\) до точки \((a_i, B)\). Он также построил \(m\) горизонтальных изгородей (\(0 \leq m \leq 25,000\)) в в различных позициях \(b_1 \ldots b_m\) (\(0 < b_i < B\)); каждая изгородь, проходит из \((0, b_i)\) в \((A, b_i)\). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на \((n+1)(m+1)\) регионов.

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

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

Поле представляет собой прямоугольник с угловыми вершинами в точках \((0,0)\) and \((A,B)\). ФД построил \(n\) вертикальных изгородей (\(0 \leq n \leq 2000\)) в различных позициях \(a_1 \ldots a_n\) (\(0 < a_i < A\)); каждая изгородь проходит от точки \((a_i, 0)\) до точки \((a_i, B)\). Он также построил \(m\) горизонтальных изгородей (\(0 \leq m \leq 2000\)) в в различных позициях \(b_1 \ldots b_m\) (\(0 < b_i < B\)); каждая изгородь, проходит из \((0, b_i)\) в \((A, b_i)\). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на \((n+1)(m+1)\) регионов.

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

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

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

- Он может заполнить самый маленький бидон (размера \(X\)) полностью до самого верха \(X\) единицами молока, и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

- Он может заполнить средний бидон (размера \(Y\)) полностью до верха \(Y\) единицами молока и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

ФД понимает, что он не всегда может полностью заполнить бидон с размером \(M\), помогите ему определить максимальное количество молока, которое он может залить в бидон с размером \(M\)

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

Для первых пяти тестов гарантируется, что \(B\) не более 100. Во всех тестах гарантируется, что \(B\) не более 1,000,000.

ФД хочет разместить ровно \(r_i\) а каждой комнате \(i\) (\(1 \leq r_i \leq 100\)). Чтобы загонять коров в амбар он планирует открывать внешнюю дверь в одну из комнат, позволяя всем коровам зайти через эту дверь. Каждая из коров затем идёт по часовой стрелке через все комнаты пока не добредёт до своей. ФД хочет открыть такую внешнюю дверь, чтобы все коровы вместе прошли минимальное суммарное расстояние. Определите это минимальное суммарное расстояние, если ФД выберет дверь для открывания оптимальным образом. Расстояние, которое проходит одна корова, равно количеству внутренних дверей, через которые она прошла.

Беси и её подружки участвуют в чемпионате. Всего имеется N (1 <= N <= 2000) команд. Каждой команде назначено уникальное ID в интервале 1...2^30-1. Чемпионат с выбыванием - после каждой игры ФД выбирает, какая команда выбывает из турнира, и она больше не участвует ни в каких играх. Турнир заканчивается, когда остаётся ровно одна команда.

ФД заметил необычное свойство счёта в матчах: В любой игре суммарный счёт двух команд всегда будет побитовым исключающим ИЛИ (XOR) ID этих команд. Например, если играют команды с ID 12 и 20, то 24 очка будет набрано в этой игре, поскольку 01100 XOR 10100 = 11000.

ФД верит, что чем больше очков набрано в игре, тем интереснее игра. Поэтому он хочет выбрать такую серию игр, чтобы максимизировать суммарное набранное количество очков. Помогите ФД организовать такие матчи.

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

Первая строка содержит одно целое число N. Последующие N строк содержат N ID команд.

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

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

Примечание Один способ набрать 37 таков: 3 и 9, 9 выиграла. В турнире остаются 6 9 10. Затем 6 и 9, побеждает 6. Остаются 6 и 10. Наконец 6 и 10 и 10 побеждает. Общее количество очков: (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37. Замечание: Побитовый XOR, чато обозначаемый ^, это побитовая операция, которая выполняется независимо над каждой позицией двух двоичных представлений целых чисел. 1 в позиции получается только если в этой позиции в разных числах находятся разные значения (1 и 0 или 0 и 1). Например 10100 (десятичное 20) XOR 01100 (десятичное 12) = 11000 (десятичное 24)

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

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

1) Вы прыгаете на квадрат c другим числом

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

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

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

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

Первая строка ввода содержит целые числа R, C, K. Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.

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

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

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

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

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

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

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

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

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

Фермер Джон купил подписку журнала 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