Информатика

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

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

Ферма Джона представляет собой решётку из \(N \times N\) квадратных полей (\(3 \leq N \leq 100\)), и \(N-1\) дороги "север-юг" и \(N-1\) дороги "запад-восток", проходящих внутри фермы и служащих разделителями между полями. Высокий забор вокруг фермы по её внешнему периметру, препятствует выходу коров за пределы фермы. Беси может свободно перемещаться с любого поля на любое соседнее поле (на север, юг, запад, восток). Ей требуется \(T\) единиц времени на переход дороги (\(0 \leq T \leq 1,000,000\)).

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

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

Кк известно, коровы - существа привычки, и они пересекают дорогу одним и тем же способом каждый день. Каждая корова входит на поле в точке, отличной от той, в которой она выходит с поля и все эти точки отличаются друг от друга. У ФД ровно 26 коров, которые лениво названы от A до Z и поэтому на поле имеется ровно 52 точки. ФД записал эти точки по часовой стрелке, записав букву - имя коровы, для которой эта точка. В результате ФД получил строку из 52 символов, в которой каждая буква алфавита встречается ровно дважды. Он не записывал, какая точка для входа, какая - для выхода.

Разглядывая свою карту точек, ФД заинтересовался, сколько раз могут пересечься пути различных пар коров. Он называет пару коров \((a,b)\) "пересекающейся" парой, если путь коровы \(a\) от входа к выходу должен пересечь путь коровы '\(b\)' от входа к выходу. Помогите ФД посчитать общее количество пересекающихся пар.

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

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

- Он может заполнить любой бидон полностью

- Он может опорожнить полностью любой бидон.

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

ФД понял, что он может и не отмерять ровно \(M\) единиц молока, в двух бидонах. Помогите ему определить минимальную разность между \(M\) и суммарным молоком в двух баллонах. То есть, определите минимальное значение \(|M-M'|\) такое, что ФД может получить \(M'\) единиц молока в сумме содержимого двух бидонов.

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

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

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

ФД хочет выбрать \(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)\) регионов.

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

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

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

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

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

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

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