Информатика

Поле представляет собой прямоугольник с угловыми вершинами в точках \((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)\) регионов.

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

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

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

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

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

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

- Он может заполнить самый маленький бидон (размера \(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 (обозначающих соответтсвенно красный или синий квадрат)

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

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

Беси стоит перед огромным камнем в середине своего любимого поля. На камне - шифровка на древнем языке, алфавит которого состоит только из трёх букв 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\), в этой бесконечной строке.

Напомним, подпоследовательность это подмножество \(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
  ^         ^ ^ ^

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

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

Коровы, последовательно пронумерованные \(1 \ldots N\) (\(1 \leq N \leq 100,000\)), организовали компанию в виде дерева, где корова 1 - президент (корень дерева). Каждая корова, кроме президента, имеет ровно одного менеджера (её родитель в дереве). Каждая корова \(i\) имеет различный професиональный рейтинг \(p(i)\), который описывает насколько хорошо она делает свою работу. Если корова \(i\) есть менеджер коровы \(j\), то мы говорим, что корова \(j\) подчиняется корове \(i\).

К несчастью коровы обнаружили что часто бывает так, что менеджер имеет меньший уровень профессиональности, чем некоторые из его подчинённых. В этом случае менеджер должен рассмотреть продвижение этих подчинённых. Ваша задача - помочь коровам узнать, когда это случается. Для каждой коровы \(i\) в компании вычислите количество подчинённых \(j\) таких, что \(p(j) > p(i)\).

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. \(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

ФД хочет, чтобы фотография получилась красивее. Он считает, что корова \(i\) выглядит несбалансированно, если \(L_i\) и \(R_i\) отличаются более чем в 2 раза. Здесь \(L_i\) и \(R_i\) - количества коров, которые выше чем корова \(i\), слева и справа соответственно. То есть, корова \(i\) является несбалансированной, если большее из чисел \(L_i\) и \(R_i\) строго более чем в 2 раза больше, чем меньшее из этих двух чисел.

Вычислите сколько всего есть несбалансированных коров.

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

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

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

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

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

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

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