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

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

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

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

ФД хочет разместить ровно \(r_i\) а каждой комнате \(i\) (\(1 \leq r_i \leq 100\)). Чтобы загонять коров в амбар он планирует открывать внешнюю дверь в одну из комнат, позволяя всем коровам зайти через эту дверь. Каждая из коров затем идёт по часовой стрелке через все комнаты пока не добредёт до своей. ФД хочет открыть такую внешнюю дверь, чтобы все коровы вместе прошли минимальное суммарное расстояние. Определите это минимальное суммарное расстояние, если ФД выберет дверь для открывания оптимальным образом. Расстояние, которое проходит одна корова, равно количеству внутренних дверей, через которые она прошла.

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

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

Имеется \(N\) стогов сена расположенных в целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\) в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги сена в диапазоне \(x-R \ldots x+R\).

Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\). Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\) коров разрушить все стоги сена на сцене.

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

Ферма представлена двумерной решёткой квадратных ячеек. AL начинает одной из этих ячеек в момент времени \(t = 0\), косит траву в этой ячейке. Поэтому изначально трава выкошена только в этой ячейке. Дальнейшие действия ФД описываются последовательностью из \(N\) предложений. Например, если первое предложение "W 10" то для моментов времени от \(t = 1\) до \(t = 10\) (то есть, следующие 10 единиц времени), ФД будет продвигаться по 1 ячейке на запад, кося траву в каждой ячейке по пути.

ФД медленно косит траву настолько, что она может успеть вырасти ещё прежде чем он закончит процесс. Любая ячейка травы, которую выкосили в момент времени \(t\) вырастет снова в момент времени \(t + x\).

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

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

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

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

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

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**

Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\)) пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.

Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)). Если звезда исчезает или перемещается за границу фото, она больше не появляется на втором фото.

Беси делает фотографии до и после перемещений, но после экспериментов, она случайно наложила одну фотографию на другую. Теперь она видит белые пикселы, которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси также помнит, что на второй фотографии не появились новые звёзды, поэтому первая фотография содержит все звёзды ночного неба. Если не существует исходного положения звёзд, которое может произвести финальное фото, выведите \(-1\).

У Фермера Джона есть квадратный холст, представленный решёткой из \(N\) * \(N\) ячеек, (\(2 \leq N \leq 2000\), \(N\) чётное). Он рисует по следующим правилам:

1. Сначала он делит холст на четыре равных квадранта, разделённых горизонтальными и вертикальными линиями через центр холста.
2. Далее он рисует любимую картинку в правом верхнем квадранте холста. Каждая ячейка верхнего правого квадранта или закрашена (представлено символом '#') или не закрашена (представлено символом '.').
3. Наконец, гордясь своим рисунком, он отражает его через ранее указанные вертикальные и горизонтальные линии в другие квадранты холста.

Например, предположим \(N=8\) и ФД нарисовал следующую картинку в правом верхнем квадранте на шаге 2:

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

Тогда после отображения через горизонтальные и вертикальные линии в другие квадранты на шаге 3, холст будет выглядеть так:

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

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

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

Вам задан холст после вандализма Беси, а также последовательность \(U\) (\(0\le U \leq 10^5\)) модификаций холста, каждое переключает ячейку в '.', если в ней была '#' и наоборот. Прежде каждого обновления и после каждого обновления выведите минимальное количество операций \(x\), которое требуется выполнить, чтобы отражение было удовлетворено.

ПР�МЕР ВВОДА:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

ПР�МЕР ВЫВОДА:

4
3
2
1
0
1

Следующий холст удовлетворяет условию отражения и отличается от оригинального холста на 4 операции:

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

Невозможно сделать исходный холст удовлетворяющим условию отражения испольуя менее чем 4 операции.

После обновления \((1, 3)\), холст выглядит так:

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

Требуется 3 операции, чтобы холст стал удовлетворять условию отражения.

После обновления \((2, 3)\), холст выглядит так:

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

Требуется 2 операции, чтобы сделать холст удовлетворяющим условию отражения.

Автор: Chongtian Ma

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует \(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\).

Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене. Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\)) дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены или горизонтально, или вертикально. Каждая горизонтальная или вертикальная может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\) целое число в интервале от \(0\) до \(10^9\) включительно.

ФД знает точно где каждая корова начала путешествие и время путешествия. Каждая из коров движется по следующему шаблону:

• РћРЅР° двигается РЅР° север (\(+y\)) или восток (\(+x\)) РЅР° РѕРґРЅСѓ единицу РІ секунду.
• Если РѕРЅР° РЅР° одиночной РґРѕСЂРѕРіРµ, РѕРЅР° продолжает двигаться РїРѕ ней.
• Если РѕРЅР° РЅР° пересечении РґРІСѓС… РґРѕСЂРѕРі, РѕРЅР° идёт РЅР° север, РЅР° чётной секунде путешествия Рё РЅР° восток иначе.

ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД где его коровы сейчас.

ПР�МЕР ВВОДА:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

ПР�МЕР ВЫВОДА:

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Автор: Benjamin Qi

Беси сортирует массив целых чисел собственным алгоритмом. У неё есть куча из \(N\) \((1 \leq N \leq 2\cdot 10^5)\) целых чисел \(a_1,a_2,\dots,a_N\) \((1 \leq a_i \leq 10^{11})\), которые она хочет перенести в другой массив в отсортированном порядке. Она постоянно ищет минимальный элемент в куче, удаляет его и добавляет в конец массива. Беси требуется \(p\) секунд, чтобы найти минимальный элемент в куче из \(p\) целых чисел.

ФД выделил Беси в помощь неограниченное количество коров. Беси использует их следующим образом. Она разделила все свои целые числа на две кучи: куча Беси и куча Помощниц. Для каждого числа в своей куче она выполняет алгоритм как обычно. Для каждого целого числа в куче Помощниц Беси назначает его отдельной корове. И предлагает ей поступать так. Когда корова помощница получает число \(a_i\), она должна подождать \(a_i\) секунд и затем добавить это число в конец массива. Если Беси и корова-помощница добавляют число в одно и то же время, то сначала добавляется число Беси. Если нескольким коровам-помощницам было дано одно и то же число, они добавляют копии этого числа в одно и то же время.

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

У Фермера Джона важная задача - решить какой тип сена купить для своих коров.

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

ФД хочет узнать, какие типы сена могут стать любимыми всем коровами. В один момент времени он может создать только одну фокус группу, но он может последовательно создавать сколько угодно фокус-групп, чтобы все коровы полюбили один и тот же тип сена.