Информатика

Входные данные
Даны два целых числа, каждое записано в отдельной строке.

Выходные данные
Программа должна вывести число 1, если первое число больше второго, число 2, если второе больше первого, или число 0, если они равны.

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Входные данные
В первой строке вводится N (3≤N≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i – целые числа, по модулю не превосходящие 10⁶.

Выходные данные
Вывести одно число – искомое количество точек.

Входные данные
В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Формат выходных данных

Выходные данные
Выведите одно число – величину площади приведённого многоугольника.

В кафе мороженое продают по три шарика и по пять шариков. Можно ли купить ровно k шариков мороженого?

Входные данные
Вводится число k (целое,положительное)

Выходные данные
Программа должна вывести слово YES, если при таких условиях можно набрать ровно k шариков (не больше и не меньше), в противном случае - вывести NO.

Решить в целых числах уравнение ax + b = 0.

Входные данные
Вводятся 2 целых числа: a и b.

Выходные данные
Необходимо вывести все решения, если их число конечно, “NO” (без кавычек), если решений нет, и “INF” (без кавычек), если решений бесконечно много.

Входные данные
Вводятся три строки. В одной из строк вводится фамилия, состоящая только из латинских букв (строчных или заглавных). В другой строке вводится дата рождения. В оставшейся строке вводится номер банковской карточки.

Выходные данные
Программа должна вывести также три строки. В первой строке - фамилию, во второй - дату рождения, в третьей - номер банковской карточки.

Ограничения
Тестовые примеры, на которых проверяется решение, удовлетворяют следующим ограничениям.

Фамилия записывается латинскими строчными и заглавными буквами, длина фамилии не меньше трех символов и не больше 50.

Номер банковской карточки натуральное число, состоящее не менее, чем из 5, и не более, чем из 15 цифр.

Дата рождениязаписывается в формате ДД.ММ.ГГГГ (день и месяц вводятся ровно двумя цифрами каждый, год - ровно четырьмя)

Вася записывает в клетки квадратной таблицы NxN натуральные числа по порядку, сначала заполняя первую строку слева направо, затем вторую и т.д. (см. рисунок слева). Петя заполняет такую же таблицу, расставляя числа сначала в первый столбец сверху вниз, затем во второй столбец и т.д.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

1	5	9	13
2	6	10	14
3	7	11	15
4	8	12	16

При этом оказалось, что некоторые числа и Вася, и Петя записали в одну и ту же клетку (например, число 6 записано во вторую строку второго столбца обеих таблиц).

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

Входные данные
Вводится одно число - размер таблицы.

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

Размер таблицы - натуральное число, не превосходящее 100.

Требуется вставить в данный массив на данное место данный элемент, сдвинув остальные элементы вправо.

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

Выходные данные
Вывести получившийся массив.

Требуется отсортировать массив по неубыванию методом "выбор максимума".

Входные данные
В первой строке вводится одно натуральное число, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

Дано бесконечное бинарное дерево. У дерева есть корень и бесконечное число вершин, у каждой вершины есть левый и правый сын, у всех вершин кроме корня есть отец.

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат входных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

У Вовы есть любимый магнит. Вове очень нравится играть с ним на большой поляне, которую можно представить в виде прямоугольника \(n\) на \(m\) клеток.

Однажды он пришел играть на поляну с магнитом и потерял его в одной из клеток. Вова очень расстроился, но нашел решение — в каждую клетку поляны он положил компас, стрелка которого может принимать 8 положений: вверх, вверх-вправо, вправо, вниз-вправо, вниз, вниз-влево, влево и вверх-влево. Каждому положению стрелки соответствует его номер:

Вова уже был готов к поискам, но тут вспомнил, что на поляне есть аномалия, которая инвертирует показания компасов вдоль ровно одной горизонтали и ровно одной вертикали. У компасов, которые лежат в зоне действия аномалии, стрелка смотрит строго в противоположном направлении тому, в котором она должна указывать.

Теперь Вова не знает, как ему найти свой магнит, и просит помощи у вас.

Формат входных данных
В первой строке входных данных записаны два целых числа через пробел \(n\) и \(m\) — размеры поляны (\(2 \le n, m \le 1500, nm \ge 6\)).

В следующих \(n\) строках описываются компасы на поляне.

В \(i\)-й строке записаны \(m\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le 8\)), \(j\)-е число в \(i\)-й строке обозначает направление стрелки компаса в \(j\)-й клетке \(i\)-й строки.

Формат выходных данных

В первой строке выведите два числа \(x\) и \(y\) через пробел — номер строки и столбца клетки, в которой лежит магнит.

Во второй выведите два числа \(a\) и \(b\) через пробел  — номера горизонтали и вертикали, в которых действует аномалия.

В данном тесте магнит лежит в клетке \((2, 1)\), инвертируется горизонталь номер \(3\) и вертикаль номер \(3\).

План студенческого городка некоторого университета представляет собой квадрат \(n \times n\), в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.

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

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата \(A_{i,j}\) планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат \(A_{i,j}\). Количество таких автоматов на этом пути называется избыточностью автомата \(A_{i,j}\). При этом автомат \(A_{1,1}\) находится в общежитии, а автомат \(A_{n,n}\) — в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от \(1\) до \(2n - 1\) определяет число автоматов с таким значением избыточности.

Формат входных данных
Первая строка содержит целое число \(n\) (\(2 \leqslant n \leqslant 1500\)). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате \(A_{i,j}\). Номера продуктов находятся в диапазоне от \(1\) до \(n^2\).

Формат выходных данных
Строка должна содержать \((2n-1)\) целых чисел — количество автоматов с избыточностями \(1, 2, \ldots, 2n - 1\) соответственно.

Переведите число {1} из 10-й СС в двоичную СС
 

Переведите число  {1}16  в десятичную систему счисления.

Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.

Посмотрим на следующий процесс. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После чего, для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в \(S\) на \(p(x)\). Определите, возможно ли в ходе такого процесса получить из строки \(S\) строку \(T\). При этом разные символы можно заменять на один и тот же символ или на символ, который заменяться не будет.

Например, пусть \(S =\) <<aabab>>, \(T =\) <<abbbc>>. Из \(S\) можно получить \(T\), если выбрать p(‘a’) = ‘b’, p(‘b’) = ‘c’ и заменить второе и третье вхождение ‘a’ на p(‘a’), второе вхождение ‘b’ на p(‘b’).

А если \(S =\) <<aabaс>>, \(T =\) <<bbbbb>>, то все вхождения ’a’ и ’c’ были заменены на ’b’.

Формат входных данных
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от ‘a’ до ‘z’.

Формат выходных данных
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите <<YES>>, на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите <<NO>>.

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(n\) узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая "— направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок "— в левую.

После прохождения монеты по трубке ширина этой трубки уменьшается на 1. Монета не может пройти по трубке ширины 0. Если монета достигла узла, из которого она не может дальше двигаться вниз, автомат останавливается и ждёт, когда в него бросят следующую монету.

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).

Формат входных данных
В первой строке задано число \(n\) — количество узлов в лабиринте. В последующих \(n\) строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание \(k\)-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k < a_k \leqslant n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k = u_k = 0\). Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k < b_k \leqslant n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k = w_k = 0\).

В последней строке задано целое число \(v\) (\(1 \leqslant v \leqslant n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

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

Формат выходных данных
Выходные данные должны содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число \(-1\).

 

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наименьшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

Формат входных данных
В единственной строке выведите одно число — номер окна, под которым следует разместить начало козырька.

В первом примере длина козырька равна количеству окон на этаже, поэтому существует всего одна позиция, куда его можно поставить.

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(1\), \(0\) или \(2\) сосульки.

В третьем примере возможны две позиции для козырька, но так как под окнами с \(1\)-м и \(3\)-м номерами одинаковое число сосулек, а окна с номерами \(2\) будут над козырьком в любом случае, выбираем наиболее левый вариант расположения.

Глеб устал от побитового исключающего <<или>> и решил, что пора найти новую интересную функцию. Его выбор пал на медиану. Напомним, медианой массива называется число, которое окажется посередине, если массив упорядочить по возрастанию. В рамках этой задачи для массивов чётной длины положим медиану равной левому из двух центральных в отсортированном порядке элементов.

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.

Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:

• \(1\) \(i\) \(x\) —  запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));

• \(2\) \(m\) \(l\) \(r\) —  запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).

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

В задаче присутствуют 6 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Есть шарики, пронумерованные от \(1\) до \(n\). Также поступают \(q\) запросов:

• \(add\) \(x\) - добавить в дек шарик с номером \(x\). Вы можете положить шарик либо сверху, либо снизу дека.

• \(del\) \(x\) - удалить из дека шарик с номером \(x\). Вы находите шарик с номером \(x\) в деке, достаете все шарики НИЖЕ \(x\), удаляете шарик \(x\), потом кладете достанные шарики (без \(x\)) обратно в том же порядке.

На запросы \(1\)-го типа вы тратите \(1\) действие, а на запросы \(2\)-го типа - \(2k + 1\) действий, где \(k\) - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете \(k\) шариков, потом удаляете нижний, потом кладете достанные \(k\) шариков обратно в том же порядке).

Посчитайте, какое минимальное количество действий вы можете потратить.

Формат входных данных
Первая строка содержит числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10^5\)) - максимальный номер шарика и количество запросов. Далее следуют \(q\) строк в формате:

• \(add\) \(x\) - добавить шарик с номером \(x\) (\(1 \leq x \leq n\)) в начало или конец дека.

• \(del\) \(x\) - удалить шарик с номером \(x\) (\(1 \leq x \leq n\)) из дека.

Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика \(x\), то он присутствует в деке в данный момент.

Формат выходных данных
Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.

Замечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.