Задачи на моделирование

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(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}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

ФД собирается делать так. Он выбирает положительное целое число \(X\). А затем повторяет следующую процедуру каждый день:

1. Предположим, что ФД уже отдал Беси \(G\) галлонов молока, он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
2. Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
3. Даёт Беси \(Y\) галлонов молока.

Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).

Эссе содержит \(N\) слов (\(1\le N\le 100\)), разделённых пробелами. Каждое слово имеет длину от 1 до 15 символов включительно, и состоит только из больших или маленьких латинских букв. В соответствии с правилами, эссе должно быть отформатировано специфическим образом: каждая строк должна содержать не более \(K\) (\(1\le K\le 80\)) символов, не считая пробелы. К счастью, текстовый процессор Беси может выполнять это требование при использовании следующей стратегии:

• Если Беси пишет слово которое может поместится на текущей строке, оно помещается в эту строку.
• Иначе надо переместить слово в следующую строку и продолжить пополнение этой следующей строки.

Конечно, последовательные слова в одной строке должны быть разделены ровно одним пробелом. Не должно быть пробелов в конце любой строки.

К несчастью, текстовый процессор Беси сломался, помогите ей отформатировать её эссе в соответствии с вышеописанными правилами.

На этот раз он делает фото с воздуха. Он хочет, чтоб все его коровы смотрели в одну сторону. Сейчас коровы организованы в решётку \(N \times N\), (\(2 \leq N \leq 1000\)) внутри квадратного пастбища, как показано ниже:

RLR
RRL
LLR

Здесь 'R' означает, что корова смотри вправо, 'L' означает, что корова смотрит влево. Поскольку коровы находятся в стаде, ФД не может говорить повернуться одной корове. Всё что он может - это повернуть целую строку или целый столбец повернув коров 'L' на 'R' или 'R' на 'L' внутри этой строки/столбца. ФД может поворачивать столбцы и строки сколько угодно раз, в том числе и поворачивать один тот же столбец или строку более чем один раз.

Как оказалось, ФД не может перевернуть всех коров в одном направлении, Но может всех коров кроме одной - определите эту корову.

Беси рассматривает решётку \(N \times N\) ячеек, где каждая ячейка имеет высоту. Каждая ячейка вне этой решётки считается имеющей бесконечную высоту.

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

Более формально:

• Множество ячеек называется "смежными с торцевой", если можно достичь любую ячейку этого множества из любой двигаясь вправо, влево, вверх, вниз.
• Множество ячеек называется "точечно-смежным" если можно из любой ячейки множества достичь любой другой ячейки множества, двигаясь, влево, вправо, вверх, вниз или по диагонали.
• Регион - это непустое множество ячеек "смежных с торцевой".
• Регион называется дырявым, если дополнение региона (которое включает бесконечные ячейки вне решётки) не является "точечно-смежным".
• Граница региона - это множество ячеек, ортогонально соседних (вверх, вниз, влево, вправо) к некоторой ячейке региона, но не принадлежащих региону.
• "Долина" это любой недырявый регион, в котором каждая ячейка имеет высоту ниже чем каждая ячейка границы долины.

Цель Беси - определить сумму размеров всех долин.

oo.
ooo
..o

oo.
oo.
..o

ooo
o..
o..

ooo
o.o
ooo

ooo
o.o
oo.

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

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

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

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

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

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

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

Сначала Беси кладёт три перевёрнутые ракушки на стол и маленький круглый камешек под одну из них. Затем Беси меняет пары ракушек, а Эльза пытается угадать где камешек.

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

Однако в этой игре Эльза не видит начальное положение камушка, но она может угадывать положение камешка. Беси, зная правильный ответ, даёт Эльзе счёт в конце, равный количеству правильных угадываний Эльзой.

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

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

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

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

К несчастью, ФД уронил свои датчики в молоко, и теперь они работают не очень хорошо. Вместо вывода точного значения трафика, датчик теперь выдаёт диапазон возможных значений. Например, датчик может показывать диапазон \([7, 13]\), означающий, что плотность трафика на этом участке не меньше чем 7 и не больше чем 13.

Шоссе вдоль фермы имеет протяжённость в \(N\) миль и движение происходит в одном направлении от мили 1 к миле \(N\). ФД хочет установить \(N\) датчиков, по одному на каждом одномильном сегменте шоссе. В некоторых из этих сегментов имеются пандусы для въезда, которые позволяют трафику вливаться на шоссе; в каждом из таких случаев ФД устанавливает свой датчик так, чтобы измерять (примерно) входящий трафик. В некоторых сегментах имеются пандусы для выезда, здесь ФД устанавливает датчик так, чтобы измерять выходящий трафик. Каждый сегмент содержит не более одного пандуса. Если на сегменте нет пандусов, ФД устанавливает датчик на собственно шоссе.

По заданным показаниям \(N\) датчиков, определите наиболее точно диапазоны, описывающие движение на шоссе от мили 1 к миле \(N\). Эти диапазоны должны не противоречить показаниям всех \(N\) датчиков.

ФОРМАТ ВВОДА:

4
on 1 1
none 10 14
none 11 15
off 2 3

ФОРМАТ ВЫВОДА:

10 13
8 12

В этом примере, комбинация считываний датчиков с сегментов 2 и 3 сужает интервал до \([11, 14]\), поскольку только показания в этом интервале соответствуют обоим считываниям \([10,14]\) и \([11,15]\). На миле 1 ровно значение 1 представляет входящий трафик, поэтому входящий трафик может быть в диапазоне \([10, 13]\). На миле 4 от 2 до 3 единиц потока может покинуть трафик, поэтому выходной поток после мили 4 может быть \([8,12]\).

Автор: Brian Dean

Чтобы улучшить свои фигуры коровы занялись гимнастикой. Фермер Джон назначил любимую корову Бесси тренером для \(N\) других коров. В каждом из \(K\) практических занятий (\(1 \leq K \leq 10\)), Бесси ранжирует \(N\) коров в соответствии с их результатами (\(1 \leq N \leq 20\)).

Сейчас она интересуется состоятельностью этих ранжировок. Пара различных коров называется "состоятельной", если одна корова выполняла лучше другой все практические упражнения.

Помогите Бесси вычислить количество состоятельных пар.

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

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

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(t=1000\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

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

Ферма Джона построена вдоль длинной прямой дороги, поэтому любое место фермы может быть описано его позицией на этой дороге (точка на числовой прямой). Телепортер описывается двумя числами \(x\) и \(y\), которые обозначают, что навоз из точки \(x\) может быть мгновенно телепортирован в точку \(y\) и наоборот.

ФД хочет транспортировать навоз из точки \(a\) в точку \(b\), и он может использовать телепортер в этом процессе (или не использовать, если он не поможет). Помогите ФД определить минимальное расстояние, которое он должен провести навоз на тракторе.

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

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

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

Игра Му-Му происходит на высокой узкой решётке из \(N\) ячеек в высоту и (\(1 \leq N \leq 100\)) и 10 ячеек в ширину. Вот пример для \(N = 6\):

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9 различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.

Две ячейки принадлежат одному и тому же связному региону, если они имеют общую вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0. Каждый раз, когда регион начинает содержать \(K\) или более ячеек, все его стоги сена исчезают - превращаются в 0. Если в один момент времени существует несколько таких регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации могут снова образоваться региона размера не менее \(K\) ячеек. В этом случае они также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион, в котором не менее \(K\) стогов.

По заданной конфигурации доски для Му-Му вычислите финальную картинку доски после выполнения всех операций.

У ФД \(N\) коров (\(1 \leq N \leq 100\)), последовательно пронумерованных \(1 \ldots N\). I-ую корову необходимо доить в интевале от времени \(s_i\) до времени \(t_i\), и для дойки требуется \(b_i\) бидонов. Процесс дойки нескольких коров может проходить в одно и то же время. Если так, то не могут использоваться одни и те же бидоны для дойки разных коров. То есть, бидон, назначенный корове \(i\) не может для дойки других коров во время от \(s_i\) до \(t_i\). Вне этого временного окна, этот бидон может быть использован для дойки других коров. Для того, чтобы упростить себе работу, ФД обеспечивает, что в любой момент времени не более одна корова начинает или заканчивает дойку. (то есть все \(s_i\) и \(t_i\) различны)

У ФД есть место, где храняться все бидоны, последовательно пронумерованные 1, 2, 3 ... В текущей стратегии дойки, когщда некоторая корова (например корова \(i\)) начинает дойку (в момент времени \(s_i\)) ФД идёт в комнату хранения, берёт \(b_i\) баллонов с наименьшими номерами и назначает их для дойки коровы \(i\).

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

К счастью, у ФД есть хорошая идея. Его три лучшие коровы Беси, Эльза и Милдред дают молоко различного вкуса. Поэтому он планирует смешивать молоко для получения совершенного вкуса.

Чтобы смешать три различных вида молока, он берёт три бидона с молоком - по бидону от каждой коровы. Эти бидоны могут иметь различные размеры и могут быть заполнены не полностью. Он переливает часть молока из бидона 1 в бидон 2, затем из бидона 2 бидон 3, затем из бидона 3 в бидон 1, снова из бидона 1 в бидон 2 и т.д. циклически. Всего он выполняет 100 таких операций. (100-ая будет как раз из бидона 1 в бидон 2). Когда ФД переливает молоко из бидона \(a\) в бидон \(b\), он переливает переливает молоко пока это возможно то есть или пока бидон \(a\) станет пустым, или бидон \(b\) станем полным.

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

Он решил учить их танцу "Bovine Shuffle". Этот танец состоит из \(N\) коров (\(1 \leq N \leq 100\)) выстроенных в ряд в некотором порядке, после которого они снова будут выстроены в ряд, возможно в другом порядке. ФД отметил позиции \(1 \ldots N\), и первая корова становится на позицию 1, вторая - на позицию 2, ..., последняя на позицию \(N\).

Перестановка описывается N числами \(a_1 \ldots a_N\), где корова из позиции i перемещается на позицию \(a_i\) во время перестановки (и конечно каждое \(a_i\) есть число от 1 до N). Каждая корова двигается на свою новую позицию во время перестановки. К счастью, все \(a_i\) различны, поэтому никакие две коровы не пойдут в одну и ту же позицию во время перестановки.

Каждой из коров ФД назначен уникальный ID из 7 цифр. Вам даётся порядок коров после трёх перестановок, определите начальный порядок.

35 Bessie -2
14 Mildred +3

Первая строка означает, в что в день 35 Bessie дала на 2 галлона меньше, чем во время последнего измерения. Следующая строка означает, что в день 14 Mildred дала на 3 галлона молока больше, чем во время последнего измерения. ФД делает не больше одного измерения в день. К несчастью, записи идут у него не обязательно в хронологическом порядке.

Для мотивации коров, ФД отображает на стене амбара карточку коровы, которая сейчас даёт больше всех молока. (Если таких коров несколько, он отображает все карточки). Определите количество дней, в которые ФД должен будет менять это отображение.

Форма этой коровы описывается решёткой из \(N \times N\) символов (\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют часть коровы, а символы '.' не части коровы.

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

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

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

ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\). Форма каждого из кусков необязательно состоит из связного региона символов '#'. Но при сдвиге все они сдвигаются на одинаковое количество позиций.