Информатика

Ферма Джона представляет собой квадратную решётку из \(N \times N\) полей (\(2 \leq N \leq 100\)). Определённые пары соседних полей (север-юг или запад-восток) разделены дорогами, и высокий забор идёт вокруг периметра всей решётки, не давая коровам возможности покинуть ферму. Коровы могут свободно перемещаться с любого поля на любое соседнее поле (на сервер, юг, запад, восток), хотя они предпочитают переходить дороги только когда это абсолютно необходимо.

Имеется \(K\) коров (\(1 \leq K \leq 100, K \leq N^2\)) на ферме, каждая расположена в различном поле. Пара коров называется "далёкой", если для того чтобы одна корова смогла посетить другую, необходимо перейти хотя бы одну дорогу. Помогите ФД посчитать количество пар удалённых коров.

Цыплята очень занятые существа и имеют ограниченное время для помощи коровам. Всего имеется \(C\) цыплят на ферме (\(1 \leq C \leq 20,000\)), последовательно пронумерованных \(1 \ldots C\), и каждый цыплёнок \(i\) может помогать коровам ровно время \(T_i\). Коровы никуда не торопятся. Всего имеется \(N\) коров на ферме (\(1 \leq N \leq 20,000\)), последовательно пронумерованных \(1 \ldots N\), и корова \(j\) способно переходить дорогу между временами \(A_j\) и \(B_j\). В идеале корова \(j\) хочет найти цыплёнка \(i\), который поможет её перейти через дорогу. Для того, чтобы их расписания были совместимы, необходимо чтобы выполнялось неравенство \(A_j \leq T_i \leq B_j\).

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

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

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

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

ФД хочет минимизировать количетво пересекающихся пар пород. По логистическим причинам ФД может перемещать коров "по кругу" на одной стороне дороги, так что поля осуществляют "циклический сдвиг". То есть для некоторого \(0 \leq k < N\), каждая корова перемещается на \(k\) полей вперёд, а коровы из последних \(k\) полей пермещаются в первые \(k\) полей. Например, если поля на одной стороне дороги упорядочены так: 3, 7, 1, 2, 5, 4, 6 и выполняется сдвиг на \(k=2\), то новый порядок будет такой: 4, 6, 3, 7, 1, 2, 5. Определите минимальное возможное количество пересекающихся пар пород, которые могут существовать после соответствующего циклического сдвига полей на одной стороне дороги.

Как известно, коровы - существа привычки, поэтому они переходят дорогу одним и тем же способом каждый день. Каждая корова приходит в поле в точке, отличающейся от той, в которой она с него уходит, и все эти точки для разных коров также отличаются друг от друга. У ФД есть \(N\) коров, последовательно пронумерованных \(1 \ldots N\), Поэтому имеется ровно \(2N\) точек у дороги. ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав последовательность из \(2N\) чисел, каждое из которых встречается в этой последовательности ровно дважды. Он не записывал, является ли эта точка точкой входа или точкой выхода.

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

Длинная дорога проходит через ферму Джона. Имеется последовательность из \(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.