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

**Замечание: Время на тест в этой задаче 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\).

Каждый день они выпускают новый пазл. Пазл представляет собой решётку 3*3, гже каждая клетка занята коровой определённой породы. Всего имеется 26 различных видов пород, которые представляются большими латинским буквами от A до Z. Играющий должен узнать тип породы в каждой клетке через серию запросов. В каждом запросе от представляет 3*3 латинских букв. Ответ формируется следующим образом: если буквы угаданы, они подсвечиваются зелёным, Буквы верной породы, но не на своём месте подсвечиваются жёлтым.

Количество подсвеченных указывает, сколько их должно быть. Например, предположим, что гипотеза содержит 4 символа A, а правильный ответ содержит только 2 символа A, причём ни одна позиция не угадана. Тогда в ответе на этот запрос только 2 символа A будут подсвечены жёлтым. В общем случае, если \(x\) коров определённой породы в запросе и только \(y\) - в правильном ответе (не считая коров, которые уже стоят на своём месте и будут подсвечены зелёным), только \(y\) из этих \(x\) коров будут подсвечены жёлтым.

По заданным правильному ответу и запросу вычислите количество квадратов, подсвеченных зелёным цветом и количество квадратов, подсвеченных жёлтым цветом.

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Например, если ввод в эту программу есть "10" (то есть, \(b[0] = 1\) и \(b[1] = 0\)), тогда вывод должен быть 1

Эльза должна сказать правильный ответ для \(M\) (\(1\le M\le 100\)) различных вводов. Бесси сейчас пытается сделать "реверс инжиниринг" для программы Эльзы. К несчастью, Эльза может и солгать - то есть не существует программы вида указанного выше, которая выведет ответы как сказала Эльза.

Для каждого из \(T\) (\(1\le T\le 10\)) подтестов определит, лгала Эльза или нет.

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

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

Каждый час корова или

• Останавливается, если трава в текущей ячейке уже съедена другой коровой.
• Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём исходном направлении.

Через некоторое время каждая корова оставит за собой колею пустых ячеек.

Если две коровы попадут одновременно на одну и ту же ячейку с травой, они поедят вместе и продолжат движение в своих направлениях в следующий час.

ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\), тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\) остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\) также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова "виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите количество остановленных ею коров.

Чтобы было понятнее относительно направлений и координат, если корова в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\), а если на восток - то в ячейку \((x+1, y)\).

У Элзи есть три положительных целых числа \(A\), \(B\), \(C\) (\(A\le B\le C\)). Эти целые числа предполагаются как секретные, поэтому она не говорит их своей сестре Беси. Вместо этого, она говорит Беси семь необязательно различных целых чисел в интервале \(1 \ldots 10^9\), подсказывая, что они есть \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\), \(A+B+C\) в некотором порядке.

По заданному списку из этих 7 чисел, помогите Беси определить \(A\), \(B\), \(C\). Можно доказать, что ответ уникален.

Главное поле фермы представлено прямой, на которой каждая корова занимает некоторое положение в целочисленной координате. Изначально все \(N\) коров находятся в различных позициях. ФД хочет, чтобы они заняли соседние позиции (например 3,4,5,6,7,8).

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

Определите минимальное и максимальное количество таких перемещений, чтобы коровы заняли \(N\) последовательных позиций.