Язык программирования

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

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

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

Недавно ФД ввёл в контест 4 дивизиона сложности: Bronze, Silver, Gold, Platinum. Все новые участники начинают в дивизионе Bronze, как только они показывают на контесте совершенный результат, они переводятся в следующий дивизион. Возможно даже, что участник переводится несколько раз в течение одного контеста. ФД хранит список всех участников и их текущий дивизион. Поэтому каждый начинает со своего дивизиона в любой момент контеста.

Когда ФД публикует результаты последнего контеста, он хочет включить информацию по количествам переведенных из Bronze в Silver, из Silver в Gold, из Gold в Platinum. Однако он затрудняется считать перемещения, если они происходят в течение одного контеста. Беси поняла, что ФД может выводить количество случившихся перемещений непосредственно из количества участников в каждом уровне до и после контеста. Помогите ей выполнить эти вычисления.

Когда дощечки лежат на земле, видно \(N\) слов. Переворачивая таблички можно получать различные множества из \(N\) слов. Чтобы помочь коровам запомнить буквы, ФД хочет подготовить некоторое количество деревянных блоков, на каждом из которых выписана одна буква алфавита. Он хочет подготовить достаточное количество блоков с каждой буквой, для того чтобы вне зависимости от того, какое множество из \(N\) слов показывается, коровы могли составить все слова используя эти блоки. Например, если \(N=3\) и на табличках представлены слова 'box', 'cat', 'car', коровам нужно как минимум 1 'b', 1 'o', 1 'x', 2 'c', 2 'a', 1 't', 1 'r'.

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

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

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

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

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

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

Беси стоит пере двумя стогами сена. Первый содержит \(a\) снопов, второй - \(b\) снопов \(1\le a,b\le 10^{18}\)).

Она должна превратить их в стоги с \(c\) и \(d\) снопами - ни больше, ни меньше.

Беси может выполнять только такие два заклинания:

• Увеличить размер первого стога РЅР° количество СЃРЅРѕРїРѕРІ РІРѕ втором стоге.
• Увеличить размер второго стога РЅР° количество СЃРЅРѕРїРѕРІ РІ первом стоге.

Для каждого из \(T\) (\(1\le T\le 10^4\)) независимых подтестов, выведите минимальное количество операций, чтобы добиться нужного результата, или если это невозможно, выведите -1.

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

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

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

-1
3
-1
0

В первом подтесте невозможно, посокльку изначально \(b>d\), разрешённые операции могут только увеличивать \(b\).

Во втором подтесте изначально стоги имеют \((5, 3)\) снопов. Беси может увеличить первый стог на количество снопов во втором получит \((8, 3)\). Затем увеличит количество второй стог на новое количество снопов в первом, получит \((8, 11)\) Затем сделает эту операцию ещё раз и получит \((8, 19)\) � это минимальное количество операций, чтобы получить данный результат.

Заметим, что в третьем подтесте ответ не такой как во втором, потому, что \(c\) и \(d\) поменяны местами (порядок куч имеет значение).

В четвертом подтесте не требуется выполнять операции.

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

1
1 1 1 1000000000000000000

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

999999999999999999

Автор: Benjamin Qi

Ответьте на \(Q\) (\(1\le Q\le 10^5\)) независимых запроса следующего вида:

Вам даны четыре целых числа \(a,b,c,d\) (\(-10^{18}\le a,b,c,d\le 10^{18}\)). За одну операцию Вы можете сделать либо \(a\mathrel{+}=b\), или \(b\mathrel{+}=a\) Определите минимальное количество операций чтобы трансформировать \((a,b)\) в \((c,d)\), если это невозможно сделать, выведите \(-1\).

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

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

Беси вернулась в школу. Она начала делать домашнюю работу по математике, в которой требуется округлить положительные целые числа до степени \(10\).

Чтобы округлить положительное целое число \(a\) к ближайшему \(10^b\), где \(b\) положительное целое число, Беси сначала находит \(b\)-ую цифру справа. Пусть \(x\) обозначает эту цифру.

Если \(x \geq 5\), Беси добавляет \(10^b\) к \(a\).

Затем Беси устанавливает в \(0\) все цифры вправо от \(b\)-ой цифры.

Например, если Беси хочет округлить \(456\) к ближайшей \(10^2\) (сотне), Беси сначала находит 2-ую цифру справа - это \(5\). То есть, \(x = 5\). Затем, поскольку \(x \geq 5\), Беси прибавляет \(100\) к \(a\). Наконец Беси устанавливает в \(0\) все цифры справа начиная со второй, получается \(500\).

Однако если Беси станет округлять \(446\) до ближайшей \(10^2\), она получит \(400\).

Посмотрев на домашнюю работу Беси, Эльза придумала новый тип округления: цепочечное округления. Чтобы цепочечно округлить до ближайшего \(10^b\), Эльза сначала округляет до ближайшего \(10^1\), затем до ближайшего \(10^2\), и т.д. до ближайшего \(10^b\).

Беси думает, что Эльза ошибается, но она сильно занята со своей домашней работой, чтобы подтвердить свои подозрения. Она просит Вас посчитать сколько целых чисел \(x\), начиная с \(2\) и до \(N\) (\(1 \leq N \leq 10^{9}\)) таких, что округление его до ближайшего \(10^P\) отличается от цепочечного округления к ближайшему \(10^P\), где \(P\) - минимальное целое такое, что \(10^P \geq x\).

Беси работает в текстовом редакторе miV! Его функция "найти и заменить" позволяет ей заменить все вхождения маленькой латинской буквы \(c\) на непустую строку из маленьких латинских букв \(s\). Например, дана строка "\(\texttt{ball}\)". Если Беси выберет в качестве \(c\) символ 'l' а в качестве строки \(s\) "\(\texttt{na}\)", данная строка трансформируется в "\(\texttt{banana}\)".

Беси начинает со строки "\(\texttt{a}\)" и трансформирует её используя некоторое количество операций «найти и заменить» и получает финальную строку \(S\). Поскольку \(S\) может быть большой, она хочет узнать по заданным \(l\) и \(r\) \(1\le l\le r\le \min(|S|,10^{18})\), чему равно \(S_{l\dots r}\) - подстрока S с позиции \(l\) по позицию \(r\) включительно.

Гарантируется, что сумма \(|s|\) по всем операциям не более \(2\cdot 10^5\), и что \(r-l+1\le 2\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\)) подтестов помогите ФД получить ответ.

Беси - робокорова, также известная как корборг. Она на числовой прямой старается выстрелить по \(T\) \((1 \leq T \leq 10^5)\) целям, расположенным в различных позициях. Беси начинает в позиции \(0\) и и следует строке из \(C\) \((1 \leq C \leq 10^5)\) команд, каждая из которых одна из букв L, F, или R:

• L: Беси двигается на одну единицу влево.
• R: Беси двигается на одну единицу вправо.
• F: Беси стреляет. Если в текущей позиции Беси находится цель, она разрушается и её больше нельзя разрушить.

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

Фермер Джон вырастил \(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++).

1. Выбрать два соседних одинаковых символа и удалить их.

2. Выбрать один символ и заменить его на два других символа в любом порядке.

В задаче требуется дать ответ для \(Q\) (\(1\le Q\le 2\cdot 10^5\)) подстрок строки \(s\).