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

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

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

Беси прыгает вдоль числовой прямой длины \(N\) \((1 \leq N \leq 10^5)\) по позициям \(1,2,\dots,N\) слева направо. Она начинает в позиции \(S\) \((1 \leq S \leq N)\) прыжком вправо со стартовой энергией \(1\). Если энергия Беси равна \(k\), то её следующий прыжок будет на \(k\) единиц вперёд от её текущей позиции.

Каждая целочисленная позиция от \(1\) до \(N\) это или цель, или прыжковая площадка. Каждая цель или прыжковая площадка имеет целочисленную величину от \(0\) до \(N\) включительно. Прыжковая площадка со значением \(v\) увеличивает энергию Беси на \(v\) и изменяет на противоположное направление прыжков. Цель со значением \(v\) будет сломана, если на неё приземлится Беси с энергией не менее \(v\). Приземление на цель не изменяет энергию и направление Беси. Сломанная цель остаётся сломанной, но Беси может на неё прыгать, энергия и направление не меняются.

Если Беси будет прыгать бесконечное количество времени или до тех пор, пока Беси покинет этот отрезок прямой, сколько целей она сломает?

Если Беси начинает на цели, которую она может сломать, она немедленно делает это. Аналогично, если Беси начинает на прыжковой площадке, то эффект площадки применяется перед первым прыжком.

\(N\) \((1 \leq N \leq 5 \cdot 10^5)\) коров Фермера Джона выстроены в круг. \(i\)-ая корова имеет ведро с целой вместимостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально полные.

Каждую минуту корова \(i\) передаёт всё молоко из своего ведра корове \(i+1\) для \(1\le i<N\), а корова \(N\) передаёт своё молоко корове \(1\). Все обмены проходят одновременно (то есть, если корова отдаёт \(x\) литров молока и также получает \(x\) литров молока, её количество молока не изменяется). Если количество молока у коровы \(i\) превысит значение \(a_i\), тогда лишнее молоко теряется.

После каждой из минут \(1, 2, \dots, N\) - сколько молока останется у всех коров вместе?

\(N\) \((1 \leq N \leq 10^5)\) коров Фермера Джона выстроены в ряд. \(i\)-ая корова имеет метку \(a_i\) (\(1 \leq a_i \leq N\)). Группа коров может сформировать дружескую группу, если все они имеют одну и ту же метку и каждая корова находится в пределах \(x\) коров от остальных коров группы, где \(x\) - целое число из интервала \([1,N]\). Каждая корова должна быть точно в одной дружеской группе.

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

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

Чтобы отпраздновать начало весны, \(N\) коров фермера Джона (\(1 \leq N \leq 2 \cdot 10^5\)) придумали новый интригующий танец, в котором они встают в круг и перестраиваются предсказуемыv способом.

В частности, по кругу есть \(N\) позиций, пронумерованные последовательно от \(0\) до \(N-1\), причем позиция \(0\) следует за позицией \(N-1\). На каждой позиции находится корова. Коровы также последовательно нумеруются от \(0\) до \(N-1\). Изначально корова \(i\) находится в позиции \(i\). Вам сообщают набор из \(K\) позиций \(0=A_1<A_2< \ldots< A_K<N\), которые являются «активными», что означает, что коровы в этих позициях будут двигаться следующими (\(1 \leq K \leq N\)).

В каждую минуту танца происходят две вещи. Во-первых, коровы в активных позициях меняются: корова в позиции \(A_1\) перемещается в позицию \(A_2\), корова в позиции \(A_2\) перемещается в позицию \(A_3\) и так далее, с коровой в позиции \(A_K\) переход на позицию \(A_1\). Все эти \(K\) перемещения происходят одновременно, поэтому после завершения вращения все активные позиции по-прежнему содержат ровно одну корову. Далее смещаются сами активные позиции: \(A_1\) становится \(A_1+1\), \(A_2\) становится \(A_2+1\) и так далее (если \(A_i = N-1\) для некоторой активной позиции, то \(A_i\) возвращается к \(0\)).

Рассчитайте порядок коров после \(T\) минут танца (\(1\le T\le 10^9\)).

Однако фермер Джон узнает о плане и пытается перехватить их беседу. Таким образом, некоторые буквы \(S\) равны \(F\), что означает, что фермер Джон запутал сообщение и отправитель неизвестен.

Уровень возбуждения незапутанной беседы – это количество повторных отправок коровы, то есть количество вхождений подстроки \(BB\) или \(EE\) в \(S\). Вы хотите найти уровень возбуждения исходного сообщения, но вы не знаете, какие из сообщений фермера Джона на самом деле были сообщениями Бесси. / Элси. По всем возможностям выведите все возможные уровни возбуждения \(S\).

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

4
BEEF

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

2
1
2

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

9
FEBFEBFEB

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

2
2
3

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

10
BFFFFFEBFE

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

3
2
4
6

Авторыы: William Yue and Claire Zhang

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

У Фермера Джона есть большое квадратное поле из \((N+1)\times (N+1)\) (\(1\le N\le 1500\)) ячеек. Пусть ячейка \((i, j)\) обозначает ячейку в \(i\)-ой строке сверху, и в \(j\)-ом столбце слева. В каждой ячейке \((i, j)\) живёт по одной корове (\(1 \le i, j \le N\)), и каждая ячейка содержит указатель или вправо или вниз. Также каждая ячейка \((i, j)\) такая, что \(i=N+1\) или \(j=N+1\), кроме \((N+1, N+1)\), содержит бак с коровьей едой. Каждый чан содержит еду различной цены. Чан в ячейке \((i, j)\) стоит \(c_{i, j}\) (\(1 \le c_{i,j} \le 500\)).

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

Чтобы поддержать свой бюджет, ФД хочет узнать общую стоимость еды съедаемой коровами каждый день. Однако, каждый день перед обедом корова в некоторой ячейке \((i, j)\) меняет направление указателя "вправо" на "вниз" или наоборот. Этот знак остаётся в таком направлении и в последующие дни, пока не будет перевёрнут обратно позже.

Вам даны координаты указателя, который меняется каждый день. Выведите стоимость каждого дня (всего \(Q\) дней, \(1 \le Q \le 1500\)).

Фермер Джон дал Беси \(Q\) строк (\(1 \leq Q \leq 100\)), состоящих только из символов 'M' и 'O.' Любимое слов Беси "MOO", поэтому она хочет преобразовать каждую из этих строк в строку "MOO" используя следующие операции

1. Заменить первый или последний символ на противоположный (то есть, 'M' на 'O', а 'O' на 'M' ).
2. Удалить первый или последний символ.

Для каждой строки определите минимальное количество операций, необходимых чтобы сформировать 'MOO' или выведите '-1', если это невозможно.

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 10^5\)). Каждая корова имеет породу Guernsey или Holstein. Коровы стоят в ряд пронумерованные \(1 \ldots N\).

Каждая корова записала свой список коров. А именно, список коровы \(i\) содержит диапазон коров, начиная с неё самой (коровы \(i\)) и до коровы \(E_i\) (\(i \leq E_i \leq N\)) включительно.

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

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

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером \(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\)) подтестов помогите ФД получить ответ.

Беси - голодная корова. Каждый день на обед если есть пакеты сена в амбаре, она съедает ровно один пакет. Чтобы Беси не голодала, Фермер Джон присылает в некоторые дни некоторое количество пакетов с сеном, которые прибывают утром (до обеда). В частности в день \(d_i\), ФД присылает \(b_i\) пакетов сена (\(1\leq d_i \leq 10^{14}\), \(1 \leq b_i \leq 10^9\)).

Вычислите общее количество пакетов сена, которые съест Беси в течение \(T\) дней.

**Замечание: Ограничение по памяти для этой задачи 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\) коров (\(1 \leq N \leq 3\cdot 10^5\)). К несчастью, стала распространяться болезнь.

Изначально некоторые коровы инфицированы. Каждую ночь инфицированная корова распространяет болезнь на коров соседних слева и справа, если они есть. Однажды инфицированная корова остаётся инфицированной.

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

Коровы Фермера Джона любят конфетные трости. У ФД \(N\) коров с определённой начальной высотой. Он хочет скормить им \(M\) конфетных тростей, различной высоты (\(1\le N,M\le 2\cdot 10^5\)).

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

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

Экран ФД небольшой, поэтому он может видеть одновременно \(K\) (\(1\le K\le \min(N,M)\)) папок и \(K\) писем одновременно. Изначально, его экран показывает папки \(1 \ldots K\) слева и письма \(1 \ldots K\) справа. Для того чтобы увидеть другие папки и письма, он должен скроллить соответствующие списки. Например, если он проскроллит вниз на одну позицию в списке папок, он увидит папки \(2 \ldots K+1\), а если проскроллит ещё на одну позицию вниз, он увидит папки \(3 \ldots K+2\). Когда ФД переносит письмо в папку, оно исчезает из списка писем, и все нижние письма поднимаются на одну позицию вверх. Например, пусть на экране отображены письма \(1, 2, 3, 4, 5\) и ФД переносит письмо 3 в соответствующую папку, тогда видимая часть списка писем станет такой: \(1, 2, 4, 5, 6\). ФД может переносить письма только в назначенные им папки.

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

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