Информатика

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует \(N\) (\(2 \leq N \leq 10^5\)) коров на эту позицию. После интервью \(i\)-го кандидата он назначает целое число "уровень компетенции" \(c_i\) от \(1\) дo \(C\) включительно (\(1 \leq C \leq 10^9\)).

Поскольку ФД интервьюировал много коров, он не помнит все \(c_i\). Однако он помнит \(Q\) (\(1 \leq Q < N\)) пар чисел \((a_j, h_j)\) где корова \(h_j\) компетенция которой была строго больше, чем уровень компетенции коров от \(1\) до \(a_j\) (\(1 \leq a_j < h_j \leq N\)).

ФД говорит Вам последовательность \(c_1, \dots, c_N\) (где \(c_i = 0\) означает, что он забыл уровень компетенции коровы \(i\), и \(Q\) пар \((a_j, h_j)\). Помогите ему определить лексикографически минимальную последовательность уровней компетенции, соответствующую этой информации или указать, что такой последовательности не существует. Последовательность чисел называется лексикографически меньше другой последовательности если в ней меньшее число не первой позиции, где эти последовательности различаются.

Каждый ввод содержит \(T\) \((1 \leq T \leq 20)\) независимых подтестов. Гарантируется, что сумма \(N\) по всем подтестам не превысит \(3 \cdot 10^5\).

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером \(N \times N\) ячеек, где определённые ячейки закрашиваются, а другие - нет. Этот холст может быть представлен массивом символов \(N\times N\) (\(1\le N\le 20\)). The \(i\)-ый вход \(j\)-ой колонки массива равен символу '*', если холст содержит чернила в этой ячейке и символ '.' в противном случае.

У Беси есть план рисунка, а Фермер Джон дал ей штамп размером \(K\times K\) (\(1\le K\le N\)) который она может использовать для закраски холста размером \(N \times N\). Беси может поворачивать штамп на \(90^{\circ}\) по часовой стрелке и применять его для закраски холста в любом месте, если штамп помещается целиком на холсте. Формально, Беси выбирает такие целые числа \(i,j\), что \(i \in [1,N-K+1]\) и \(j \in [1, N-K+1]\); и затем для каждого \((i',j')\) такого, что \(1 \le i', j' \le K\), ячейка холста \((i+i'-1, j+j'-1)\) закрашивается в чёрный цвет, если в штампе было чернило в позиции \((i', j')\). Беси может поворачивать свой штамп в любой момент между закрашиваниями. Если ячейку закрасили она остаётся закрашенной навсегда.

ФД интересно может ли Беси создать свой рисунок, используя его штамп. Для каждого из \(T\) (\(1 \le T \le 100\)) подтестов помогите ФД получить ответ.

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции \(A\) и \(B\). В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени \(t\), тогда он прибудет на другую станцию в момент времени \(t+T\) (\(1\le T\le 10^{12}\)).

Имеется \(N\) (\(1\le N\le 5000\)) поездов для которых нужно установить время отправки. \(i\)-ый поезд должен покинуть станцию \(s_i\) в момент времени $t_i или позже (\(s_i\in \{A, B\}, 0\le t_i\le 10^{12}\)). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени \(a_i\ge t_i\), общая задержка определяется как \(\sum_{i=1}^N(a_i-t_i)\).

Фермер Джон вырастил \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) аспарагусов на своей ферме. Однако некоторые из этих растений имеют генетические отличия, поэтому некоторые растения растут быстрее чем другие. Изначальная высота \(i\)-го растения равна \(h_i\) дюймов и после каждого дня \(i\)-ое растение вырастает на \(a_i\) дюймов.

ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые растения были выше чем другие. Он дал Вам массив различных целых чисел \(t_1,\dots,t_N\), содержащих все целые числа от \(0\) до \(N-1\) и хочет, чтобы \(i\)-ое растение имело ровно \(t_i\) растений, которые выше этого. Определите минимальное количество дней, чтобы требование ФД было удовлетворено или укажите, что это невозможно.

Заметим, что тесты этой задачи могут потребовать использования 64-битного целого типа (например, "long long" в C/C++).

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

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

Конфигурация мороженого, которое производится машиной, может быть описано решёткой \(N \times N\) grid (\(1 \leq N \leq 1000\)):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет \(1 \times 1\) квадратную ячейку мороженого.

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

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

Главное поле фермы представлено прямой, на которой каждая корова занимает некоторое положение в целочисленной координате. Изначально все \(N\) коров находятся в различных позициях. ФД хочет, чтобы они заняли соседние позиции (например 3,4,5,6,7,8).

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

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

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

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

Определите минимальное и максимальное количество перемещений, которое возможно сделать прежде чем коровы расположатся в трёх последовательных позициях.

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

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

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

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

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно \(N\) (\(1 \leq N \leq 10^5\)) коров прибывают в аэропорт, и корова \(i\) прибывает в момент времени \(t_i\) (\(0 \leq t_i \leq 10^9\)). ФД организовал \(M\) (\(1 \leq M \leq 10^5\)) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до \(C\) (\(1 \leq C \leq N\)) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что \(MC \geq N\).