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

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

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

Беси прыгает вдоль числовой прямой длины \(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\)). К несчастью, стала распространяться болезнь.

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

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