Информатика

Натуральное число \(p\) называется простым, если оно имеет ровно два различных делителя: \(1\) и \(p\). Например, числа \(2\), \(3\), \(5\) являются простыми. Число \(1\) простым не считается.

Целое число \(p\) будем называть квазипростым, если \(p\) или \(-p\) является простым. Например, числа \(-2\), \(2\), \(-3\), \(3\), \(-5\), \(5\) являются квазипростыми.

Хотя любое натуральное число можно единственным образом представить в виде произведения простых, для целых чисел и квазипростых это уже неверно. Например, число \(12\) можно тремя способами представить в виде произведения квазипростых: \(12=2\cdot 2\cdot 3\), \(12=(-2)\cdot 2\cdot (-3)\), \(12=(-2)\cdot (-2)\cdot 3\).

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

Формат входных данных
На первой строке ввода находится число \(n\) (\(-10^9 \le n \le 10^9\), \(n \ne 0\), \(n \ne \pm 1\)).

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

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

Формат выходных данных
Выведите одно целое число — искомое число пар.

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Рассмотрим разбиения целого положительного числа \(n\) в сумму целых положительных чисел. Будем называть разбиение непростым, если слагаемые в нем упорядочены по неубыванию, причем среди слагаемых нет простых чисел.

Например, для \(n=5\) существует два непростых разбиения: \(1+1+1+1+1\) и \(1+4\).

Задано число \(n\). Выведите все его непростые разбиения на слагаемые.

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 70\)).

Формат выходных данных
Выведите все непростые разбиения \(n\) на слагаемые. Слагаемые разделяйте знаком <<+>>. Не выводите пробелы. Разбиения можно вывести в любом порядке.

Для заданного в 10-й с/с дробного числа требуется определить разницу длин целой и дробной части этого числа в 5-й с/с при переводе с точностью до 8 разрядов.
Входные данные
положительное число в 10-й с/с, целая и дробная часть которого не превышают 8 разрядов каждая. Целая и дробная части разделяются точкой. Дробная часть может отсутствовать.
Выходные данные
неотрицательное целое число - разница между количеством разрядов целой и дробной части в пятеричной системе счисления.

Примеры

№	Входные данные	Выходные данные	Примечание
1	8.4	1	8.410=13.25, количество разрядов целой части на 1 больше, чем дробной
2	1.5	7	1.510=1.(2)5=1.222222225, в 5-й с/с дробь не имеет конечного представления, поэтому ограничиваем длину 8 дробными разрядами

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

Для узла c IP-адресом  253.189.9.182 адрес подсети равен 253.189.8.0. Сколько существует различных возможных значений третьего слева байта маски, если известно, что в этой сети не менее 100 узлов? Ответ запишите в виде десятичного числа.

После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру “Банковские карты”.

Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с \(n\)-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если \(n=3\) и у Шерлока номер карты \(123\), а у Мориарти \(321\), то сначала Шерлок называет число \(1\), а Мориарти называет число \(3\) и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число \(2\), и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет \(3\), а Мориарти называет \(1\) и получает щелбан.

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

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

Формат входных данных
В первой строке находится одно целое число \(n\) (\(1 \leqslant n \leqslant 1000\)) — количество цифр в банковских картах Шерлока и Мориарти.

Во второй строке записана последовательность из \(n\) цифр — номер кредитной карточки Шерлока.

В третьей строке записана последовательность из \(n\) цифр — номер кредитной карточки Мориарти.

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

Во второй строке выведите так же одно число — максимальное число щелбанов, которое Мориарти может дать Шерлоку.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n \leq 3\), наберёт не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq n \leq 8\), наберет не менее \(30\) баллов.

Формат входных данных
Первая строка содержит натуральное число N (1 < N ≤ 1 000 000) – количество месяцев существования компании и натуральное число K (1 < K < N) – минимально допустимый интервал.  В каждой из следующих N строк находится одно целое число profit_i, не превышающее по модулю 10 000 000: прибыль компании за iй месяц. 

Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее K месяцев. Гарантируется, что ответ к задаче не превышает 10⁹.

Бинарное дерево — это набор вершин, у каждой из которых может быть левый и правый ребёнок. Одна из вершин является корнем дерева, она не является ребёнком какой-то другой. Начав в корне и каждый раз переходя в одного из детей, можно дойти до любой вершины. Множество вершин, до которых можно дойти из заданной, называется её поддеревом.

У бинарного дерева есть три основных обхода: прямой (pre-order), центрированный (in-order) и обратный (post-order).

Прямой обход дерева — это порядок его вершин, полученный следующим рекурсивным алгоритмом:

1. Добавить корень дерева в обход.

2. Если у корня есть левый ребёнок, выписать прямой обход его поддерева.

3. Если у корня есть правый ребёнок, выписать прямой обход его поддерева.

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

Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число \(x\) от \(-1\) до \(1\), обозначающее, в какой момент мы выписываем эту вершину, а именно:

• \(x = -1\): до обходов поддеревьев её детей;

• \(x = 0\): между обходами поддеревьев её детей;

• \(x = 1\): после обходов поддеревьев её детей.

Таким образом, если во всех вершинах записано \(-1\), обход является прямым, если \(0\) — центрированным, если \(1\) — обратным.

Рассмотрим дерево с \(n\) вершинами, пронумерованных от \(1\) до \(n\). Корень дерева — вершина \(1\). Изначально во всех вершинах записано число \(-1\).

В рамках исследования необходимо обработать \(q\) запросов одного из следующих типов:

1. Поменять числа в вершинах \(l, l+1, \dots, r\) на \(x\) (\(x\) равен \(-1\), \(0\) или \(1\)).

2. Сообщить, на какой позиции в текущем обходе будет стоять вершина \(i\).

Необходимо вывести ответы на все запросы второго типа.

В первой строке входных данных даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)).

В следующих \(n\) строках даны по два целых числа \(L_i\) и \(R_i\) (\(0 \le L_i, R_i \le n\)) — номер левого и правого ребёнка вершины \(i\) соответственно, либо \(0\), если соответствующий ребёнок отсутствует.

Гарантируется, что \(L_i\) и \(R_i\) задают корректное бинарное дерево.

Формат входных данных
В следующих \(q\) строках даны запросы. Первое число в строке \(t\) (\(t \in \{1, 2\}\)) — тип запроса.

В случае запроса первого типа далее даны целые числа \(l\), \(r\) и \(x\) (\(1 \le l \le r \le n\), \(x\) равен \(-1\), \(0\) или \(1\)) — границы отрезка вершин, в которых меняются числа, и новое значение.

В случае запроса второго типа далее дано число \(i\) (\(1 \le i \le n\)) — номер вершины, позицию которой в обходе необходимо вывести.

Формат выходных данных
На каждый запрос второго типа выведите единственное число от \(1\) до \(n\) — позицию соответствующей вершины в обходе.

Пусть \(q_1\) — количество запросов первого типа.

• \([1, 3, 5, 2, 4]\)

• \([5, 2, 3, 4, 1]\)

• \([5, 3, 2, 4, 1]\)

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

• выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);

• выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

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

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

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

• В первой строке выведите строку <<YES>>.

• Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).

• В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

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

В третьем примере изначально дана таблица:

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

Задан массив натуральных чисел \(A = [a_1, a_2, \ldots, a_n]\). Отрезком массива \(A\) с \(l\) по \(r\) будем называть массив \([a_l, a_{l+1}, \ldots, a_r]\).

Для заданного массива \(A\) и числа \(k\) требуется найти количество пар \((l, r)\), таких что \(l \le r\) и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

На первой строке ввода заданы целые числа \(n\) "— число элементов массива \(A\) и \(k\) (\(1 \le n \le 200\,000\), \(2 \le k \le 10^9\)).

На второй строке заданы целые числа \(a_1, a_2, \ldots, a_n\) — элементы массива \(A\) (\(1 \le a_i \le 10^9\)).

Выведите одно число: количество пар \((l, r)\), таких что \(l \le r\), и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

В примере подходят следующие отрезки:

• \(l = 1\), \(r = 3\), отрезок \([1, 2, 3]\)

• \(l = 1\), \(r = 4\), отрезок \([1, 2, 3, 4]\)

• \(l = 2\), \(r = 2\), отрезок \([2]\)

• \(l = 2\), \(r = 5\), отрезок \([2, 3, 4, 5]\)

• \(l = 3\), \(r = 5\), отрезок \([3, 4, 5]\)

• \(l = 4\), \(r = 4\), отрезок \([4]\)

Рассмотрим все представления числа \(n\) в виде суммы различных целых возрастающих слагаемых: \(n = a_1 + a_2 + \ldots + a_k\), \(a_1 < a_2 < \ldots < a_k\).

Будем называть такое разбиение хаотическим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых среднее не равно среднему арифметическому крайних. Иначе говоря, для всех \(i\) от 1 до \(k - 2\) выполнено \(a_{i+1} \ne (a_i + a_{i+2}) / 2\).

Задано число \(n\). Выведите все его хаотические разбиения на слагаемые.

На ввод подается целое число \(n\) (\(1 \le n \le 80\)).

Выведите все хаотические разбиения на слагаемые числа \(n\). Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком <<+>> без пробелов.

В этой задаче 25 тестов, каждый оценивается независимо в 4 балла.

Будем называть два натуральных числа \(x\) и \(y\) непохожими, если они различны и нет двух различных отличных от \(1\) чисел \(a\) и \(b\), таких, что и \(x\) и \(y\) делятся как на \(a\), так и на \(b\). Например, 6 и 9 непохожи, так как единственное число, отличное от 1, на которое делятся оба числа "— 3. А вот числа 12 и 18 не являются непохожими, так как оба делятся на 2, 3 и 6.

Задано натуральное число \(x\), а также натуральные числа \(l\) и \(r\). Требуется найти все числа \(y\), такие что \(l \le y \le r\), и числа \(x\) и \(y\) непохожи.

Формат входных данных
На первой строке ввода задано число \(x\) (\(1 \le x \le 10^9\)).

На второй строке ввода задано число \(l\), на третьей строке ввода задано число \(r\) (\(1 \le l \le r \le 10^9\); \(r - l \le 1000\)).

Формат выходных данных
На первой строке выведите число \(k\) "— количество непохожих на \(x\) чисел на отрезке от \(l\) до \(r\), включительно.

На второй строке выведите все эти числа в возрастающем порядке.

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в ячейках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.

Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением \(i\) рассмотрим позицию \(t_i\) — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).

Назовем головоломку решаемой, если для нее существует хотя бы одна подходящая последовательность.

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

За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, которое потребуется, чтобы головоломка стала решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий \(0\), \(1\), или же не менее \(2\). В случае, когда потребуется ровно \(1\) действие, найдите также количество подходящих пар клеток для обмена чисел.

Формат входных данных
В первой строке вводятся два целых положительных числа \(n, m\) (\(1 \leq n \cdot m \leq 400\,000\)) — длины сторон таблицы.

В каждой из следующих \(n\) строках вводятся \(m\) целых чисел \(a_{i1}, a_{i2}, \dots, a_{im}\) (\(1 \le a_{ij} \le n \cdot m\)).

Гарантируется, что каждое число от \(1\) до \(n \cdot m\) встречается ровно один раз.

Формат выходных данных
Пусть \(a\) — минимальное число действий, после которых головоломка станет решаемой.

Если \(a = 0\), выведите \(0\).

Если \(a = 1\), выведите \(1\), а также количество подходящих пар клеток.

Если \(a \ge 2\), выведите \(2\).

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

Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями \((1, 5), (1, 6), (2, 6)\).

В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен \(2\).