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

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

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

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

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

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 \)-ое число, которое говорят в этой игре.

Недавно эти коровы познакомились с игрой "крестики-нолики", но им не понравилась игра только с двумя участниками, поэтому они придумали модификацию этой игры чтобы одновременно множество коров могли играть. Как и в стандартной игре, игра ведётся на доске \(3 \times 3\) , только вместо X и 0 каждый квадратик помечается символом \(A \ldots Z\) той коровы, которая сделала ход в данное поле.

Пример доски с такой игрой:

COW
XXO
ABC

Коровы заполнили все 9 квадратиков, теперь они не могут понять, кто же победил в этой игре. Понятно, как и в обычной игре "крестики-нолики", если одна корова заняла строку, столбец или диагональ, она выиграла. Однако поскольку игроков может быть больше двух, они решили позволять коровам формировать команды из двух коров. Команда объявляется победительницей, если строка, столбец или диагональ состоят только из символов коров одной команды.

Помогите коровам определить, сколько одиночных коров или команд из двух коров могут одержать победу. Заметим, что один и тот же квадратик доски может быть использова в разных вариантах объявления победы.

В некоторых целочисленных координатах имеются двухглавые разбрызгиватели, оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((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\).

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