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

Как часть исследования вопроса "почему коровы переходят дороги", Фермер Джон получить задание составить документ о том, сколько раз каждая из его коров переходила дорогу. Он тщательно залоггировал данные о местоположении каждой из его коров, и выполнил серию из \(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\).