Вывод формулы

Беси стоит пере двумя стогами сена. Первый содержит \(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\).

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

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

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

Для каждого \(1 \leq K \leq N\), помогите коровам определить количество классов эквивалентности стартовых состояний: то есть максимальное количество стартовых состояний, которое они могут выбрать, так что никакие два из них не будут эквивалентными. Поскольку эти числа могут быть очень большими, выведите их остатки по модулю \(10^9 + 7\).

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Имея немного более ограниченный словарный запас, версия FizzBuzz, которую играют коровы, включает в себя выражение «Moo» вместо Fizz, Buzz и FizzBuzz. Поэтому начало коровьей версии игры

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

По заданному числу \( N \) (\( 1 \ leq N \ leq 10 ^ 9 \)), определите \( N \)-ое число, которое говорят в этой игре.

В некоторых целочисленных координатах имеются двухглавые разбрызгиватели, оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((i,j)\) разбрызгивает воду на часть поля к северу и востоку от себя и разбрызгивает удобрения к югу и западу от себя. Формально, он поливает водой все вещественные координаты \((x,y)\) для которых \(N \geq x \geq i\) и \(N \geq y \geq j\), и удобряет все вещественные координаты \((x,y)\) для которых \(0 \leq x \leq i\) and \(0 \leq y \leq j\).

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

Помогите ФД определить количество прямоугольников с положительной площадью, на которых он может растить сладкую пшеницу. Поскольку число может быть очень большим, выводите его по модулю \(10^9 + 7\).

Сцена для шоу представляет \(N\) платформ, размещённых по кругу. На каждой платформе от \(1\) до \(N\) коров формируют стек (корова становится на корову). По сигналу главного на манеже, все стеки параллельно "падают" по часовой стрелке так, что нижняя корова стека не движется, корова на ней движется на одну платформу по часовой стрелке, следующая корова - на две платформы и т.д. В результате получаются новые стеки коров.

Главный на манеже думает, что шоу будет лучше, если после того, как стеки упадут, новый стек на каждой платформе будет содержать такое же количество коров, что и исходный стек на манеже. Мы называем конфигурацию стеков на манеже "магической", если она удовлетворяет этому условию. Вычислите количество "магических" конфигураций. Поскольку это число может быть очень большое, выведите его остаток по модулю \(10^9 + 7\).

Две конфигурации считаются различными, если существует платформа, для которых у этих двух конфигураций различное количество коров.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) (the "\(O\)" это переменная, а не 0). Для каждой из переменных она даёт ФД список до 500 целых значений, которые та может принять. Она просит ФД посчитать количество способов, получить результат, кратный числу 7.

Заметим, что ответ на эту задачу может быть слишком большим, чтобы пометситься в 32-битную переменную, рекомендуется использовать 64-битную переменную типа long long в С/С++.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) ( "\(O\)" это переменная, а не 0). Для каждой переменной она даёт ФД список до 20 целых чисел, которые эта переменная может принять. Беси просит ФД посчитать количество различных способов назначить значения переменным, чтобы вычисленное выражение было чётным числом.