реализация

• на матрицу накладывается карточка;
• далее двигаясь по каждой строке по порядку слева-направо, выписываются цифры, которые попали в прорези;
• цифр всегда 18, притом координаты всегда состоят из 8цифр (две целой части, шесть вещественной), значит два символа игнорируются и обозначают точку в вещественном числе в соответствующем порядке.

• 1 – метка в левом верхнем углу карточки;
• 2 – метка в правом верхнем углу карточки;
• 3 – метка в правом нижнем углу карточки;
• 4 – метка в левом нижнем углу карточки.

Авиакомпания <<Флагманский Флот Татарстана>> предлагает в своих самолётах новый вид бизнес-класса. Салон самолёта состоит из \(n\) мест, расположенных в один ряд вдоль прохода. Введём координатную прямую вдоль салона так, что расстояние между креслами будет равно \(1\), и места будут иметь координаты от \(1\) до \(n\).

Во время полёта стюарду нужно пройти по самолету и раздать всем пассажирам напитки. Напитки бывают \(k\) разных видов, пронумерованных числами от \(1\) до \(k\). Каждый пассажир получает одну порцию одного напитка, пассажир заказывает предпочитаемый вид напитков при бронировании билета, поэтому все предпочтения пассажиров известны заранее.

Напитки разлиты по бутылкам, каждая бутылка вмещает \(p\) порций одного напитка. В тележку для напитков можно загрузить не более \(m\) бутылок с любыми видами напитков, гарантируется, что \(m\ge k\).

Пассажиры обслуживаются в порядке возрастания номеров их мест. Первоначально тележка находится в начале салона в точке \(0\), и её можно заполнить любыми видами напитков перед обслуживанием. После завершения обслуживания тележка должна приехать в точку \(n+1\). При этом в точках \(0\) и \(n+1\) могут находиться кладовые: или одна кладовая в одном из концов салона или две кладовые в двух концах, в которых имеется достаточный запас напитков каждого вида. В этих кладовых можно выгрузить из тележки пустые бутылки и погрузить полные бутылки.

По ходу обслуживания напитки будут расходоваться, поэтому время от времени возникает необходимость пополнить запас напитков на тележке в одной из кладовых. Если в текущий момент тележка находится напротив кресла номер \(i\), то для того, чтобы доехать до кладовой в точке \(0\) необходимо проехать расстояние \(i\), а для того, чтобы доехать до кладовой в точке \(n + 1\) необходимо проехать расстояние \(n+1-i\). В кладовых можно выгрузить пустые бутылки из тележки и загрузить на свободные места бутылки с напитками любых видов. Выгружаемые бутылки должны быть пустыми, нельзя выгружать бутылки, в которых остались напитки, или выливать напитки. Нельзя переливать остатки напитков между разными бутылками. Можно загружать на тележку более одной бутылки одного вида. После этого тележка должна проехать расстояние от кладовой до кресла первого необслуженного пассажира, чтобы продолжить обслуживание.

Определите, какое минимальное расстояние должна проехать тележка, чтобы переместиться из точки \(0\) в точку \(n+1\) и обслужить всех пассажиров.

Формат входных данных
Первая строка входных данных содержит четыре целых числа \(n\), \(m\), \(k\), \(p\) (\(3 \leq n \leq 10^6\), \(1 \leq p \leq 10^6\), \(1 \leq k \leq m \leq 10^6\)) — количество мест в салоне, вместимость тележки, количество типов напитков и вместимость каждой бутылки соответственно.

В следующей строке содержится целое число \(c\) (\(1 \leq c \leq 3\)) — параметр, описывающий наличие кладовых в салоне. Если \(c=1\), то кладовая находится только в точке \(n+1\). Если \(c=2\), то кладовая находится только в точке \(0\). Если \(c=3\), то кладовые находятся в обоих концах салона.

В следующей строке содержатся \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq k\)) — типы напитков, которые заказали пассажиры.

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

Пояснения к примерам
В первом примере в тележку вмещается \(m=2\) бутылки по \(p=1\) порции в каждой. Кладовая находится в конце салона. Первоначально тележку нужно загрузить бутылками с напитками вида \(1\) и \(2\), которые будут налиты пассажирам на местах \(1\) и \(2\), тележка проедет расстояние \(2\) от точки \(0\) до точки \(2\). После этого тележке нужно будет проехать до кладовой в конце салона (расстояние \(4\)), загрузить тележку бутылками вида \(1\) и \(2\) и вернуться к креслу номер \(3\) (тележка проедет расстояние \(3\)). Пассажирам на местах \(3\) и \(4\) выдаются напитки вида \(1\) и \(2\) (тележка проезжает расстояние \(1\) от места \(3\) до места \(4\)). После этого тележке понадобится ещё раз съездить в кладовую (от кресла \(4\) до кладовой расстояние \(2\)), вернуться из кладовой до кресла \(5\) (расстояние \(1\)), и проехать ещё \(1\) до конца салона. Общее расстояние равно \(2+4+3+1+2+1+1=14\).

Во втором примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой. Кладовая находится в начале салона. Необходимо загрузить тележку тремя бутылками вида \(1\), обслужить пассажиров на местах с номерами от \(1\) до \(4\). После этого опустошатся две бутылки вида \(1\), нужно будет сразу съездить в кладовую, чтобы загрузить две бутылки вида \(2\), затем обслужить пассажиров на местах с номерами от \(5\) до \(8\).

В третьем примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой, кладовые находятся в обоих концах салона. Для обслуживания пассажиров нужны две бутылки вида \(2\) и по одной бутылке видов \(1\) и \(3\), поэтому понадобится один раз съездить в кладовую для того, чтобы заменить пустую бутылку вида \(2\) на полную. Это лучше сделать после обслуживания пассажира на месте \(3\), тележка должна съездить в кладовую в начале салона.

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

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

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из \(m\) строк и \(n\) столбцов. Доска разбита на \(m \times n\) единичных клеток размером \(1 \times 1\). На некоторых клетках стоят квадратные фишки размером \(1 \times 1\), на каждой фишке написана одна из \(26\) английских букв.

С фишками производятся \(q\) операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой \(s\) длины \(q\), состоящей из символов, соответствующих направлениям: <<L>> — влево, <<R>> — вправо, <<U>> — вверх и <<D>> — вниз.

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

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 200\,000\)). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа \(m\) и \(n\) — размеры доски (\(1 \le m, n \le 10^6\), \(1 \le m\times n \le 10^6\)).

В следующих \(m\) строках задано изначальное расположение фишек на доске.

В \(i\)-й строке (\(1 \le i \le m\)) находится строка \(a_{i1}a_{i2}\ldots a_{in}\) длины \(n\), задающая \(i\)-ю строку доски. Каждый символ \(a_{ij}\) является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если \(a_{ij}=\mbox{<<.>>}\), то клетка в \(i\)-й строке и \(j\)-м столбце является пустой, иначе в ней находится фишка, на которой написана буква \(a_{ij}\).

В последней строке заданы \(q\) символов \(s_1s_2\ldots s_q\) без пробелов, задающие последовательность операций (\(1 \le q \le 10^6\)). Каждый символ \(s_i\) является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений \(m \times n\) по всем наборам входных данных не превышает \(2\cdot 10^6\). Сумма значений \(q\) по всем наборам входных данных не превышает \(2\cdot 10^6\).

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

Обозначим через \(\sum mnq\) сумму \(mnq\) по всем наборам входных данных.

Обозначим через \(\sum mq\) сумму \(mq\) по всем наборам входных данных.

Назовем расположение фишек лестницей, если \(m=n\), \(a_{ij}={<<\texttt{.}>>}\) для всех \(1 \le i \le j \le n\) и \(a_{ij}\ne{<<\texttt{.}>>}\) для всех \(1 \le j < i \le n\). Иными словами, все фишки находятся на клетках ниже главной диагонали доски, и на каждой клетке ниже главной диагонали есть фишка.

Пояснения к примерам
В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как \(s_1={<<\texttt{L}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как \(s_2={<<\texttt{R}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как \(s_3={<<\texttt{U}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Напишите программу на Python, которая:

1. Считывает уравнения из строки, разделенных запятой.

2. Преобразует строку в символьное уравнение с помощью SymPy.

3. Решает уравнение.

4. Выводит корни уравнения.

Из нижеприведенных правил выберите правило с наибольшим приоритетом:

1) footer .social-links a[target="_blank"]
2) #footer a
3) a:hover
4) a

В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по вопросам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь организаторам необходимо распределить секции по дням: в каждый день будут проводиться 4 секции.

Известно, что в съезде примут участие \(n\) человек. Каждый участник съезда выбрал 3 секции, которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно, каждый участник в один день может присутствовать не более чем на одной секции. Поэтому если в один день будут идти две или три секции, выбранные каким-то участником, то он всё равно сможет посетить только одну из них. Если же выбранные секции будут проходить в разные дни, участник сможет посетить их все.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 10\,000\)) — количество участников съезда.

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

Формат выходных данных
Программа должна вывести \(3\) строки, в каждой из которых должны быть \(4\) числа через пробел — номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний несколько, можно вывести любое из них.

Примечание
В примере из условия расписание составлено так, что второй и третий участник посетят все желаемые секции, а первый — две секции (\(5\) и одну из секций \(1\), \(6\)). Таким образом, суммарно будут посещены 8 секций. Можно показать, что этот результат улучшить нельзя.

Однажды, девочка Аня записала несколько целых чисел лежащих в диапазоне от \(-1000\) до \(1000\) в некоторую изначально пустую строку \(S\), разделив каждые два пробелом. Но стоило ей отвернуться, как злой хулиган Гриша заменил все пробелы в строке на подстроки из строчных латинских букв. Тем не менее и этого ему показалось мало, поэтому он мог дописать латинских строчных букв еще и в начало и конец строки \(S\).

Аня очень расстроилась, увидев это безобразие, но времени на расшифровку у нее нет. Однако, ей срочно понадобилось узнать, какое число было наименьшим. Ваша задача — помочь ей.

Формат входных данных
В первой строке содержится одно натуральное число \(n\) — количество символов в строке \(S\) (\(1 \le n \le 100\)).

Во второй строке содержится строка \(S\), состоящая из латинских строчных букв, цифр и знаков <<->>.

Гарантируется:

• В данной строке содержится хотя бы одна цифра

• В следующей позиции после каждого знака <<->> находится цифра

• В числах, изначально записанных в строку не было ведущих нулей, а также каждое из них не превосходило \(1000\) по модулю.

Формат выходных данных
В единственной строке выведите наименьшее число, которое было у Ани в строке.

Обратите внимание, что \(0\) следует выводить без знака <<->>.

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

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

Формат входных данных
В первой строке дано одно число \(n\) (\(1 \le n \le 10^5\)) — количество участников игры. Далее в \(n\) строках вводятся названные участниками натуральные числа, не превосходящие \(10^9\).

Формат выходных данных
Программа должна вывести число, написанное победителем. Если победителя нет, то нужно вывести число \(-1\).

Замечание

В первом примере из условия участвовали \(7\) игроков и они назвали числа \(5\), \(1\), \(1\), \(3\), \(4\), \(3\), \(1\). Сначала оставим только те числа, которые встречаются ровно один раз: \(5\) и \(4\). Минимальное из этих чисел равно \(4\).

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

Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из \(n\) специальных платформ, пронумерованных от \(1\) до \(n\). Расстояние между \(i\)-й и \(i+1\)-й платформой равно \(d_i\), аналогично расстояние между \(n\)-й и \(1\)-й платформой равно \(d_n\).

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом \(a\). Робот может перепрыгнуть с платформы \(i\) на платформу \(i+1\), если \(a \ge d_i\). Аналогично, прыжок с \(n\)-й платформы на \(1\)-ю возможен, если \(a \ge d_n\). При этом после каждого прыжка ловкость робота увеличивается на \(1\).

Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив \(n\) прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

Формат входных данных
На первой строке ввода находится число \(n\) (\(3 \le n \le 10^7\)).

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

Если \(f = 1\), то на третьей строке находятся \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^{9}\)).

Если \(f = 2\), то на третьей строке находится число \(m\) \(\left(2 \le m \le \min(n, 10^5)\right)\) и три целых числа \(x\), \(y\) и \(z\) (\(0 \le x, y, z \le 10^9\)). На четвертой строке находятся \(m\) целых чисел \(c_1, c_2, \ldots, c_m\) (\(1 \le c_i \le 10^9\)). Значения \(d_i\) вычисляются по следующим формулам.

Если \(1 \le i \le m\), то \(d_i = c_i\).

Если \(m + 1 \le i \le n\), то \(d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1\).

Здесь \(\bmod\) означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<%>>.

Формат выходных данных
Требуется вывести два целых числа: минимальную допустимую начальную ловкость \(a\) и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

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

Замечание
Во втором примере массив расстояний между платформами равен \([1, 2, 3, 4, 5, 18, 45, 112, 273, 662]\). Значения от \(d_6\) до \(d_{10}\) вычисляются по формулам:

\(d_6 = \left((1\cdot d_4+2\cdot d_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18\)

\(d_7 = \left((1\cdot d_5+2\cdot d_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45\)

\(d_8 = \left((1\cdot d_6+2\cdot d_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112\)

\(d_9 = \left((1\cdot d_7+2\cdot d_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273\)

\(d_{10} = \left((1\cdot d_8+2\cdot d_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662\)

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(-1\), \(0\) или \(1\). Известно, что \(-1\) находятся только строго в правой половине массива, то есть на индесах от \(\left\lfloor\frac{n + 1}{2}\right\rfloor + 1\) до \(n\). Все оставшиеся элементы могут быть равны только \(0\) или \(1\).

С массивом разрешается выполнять следующие два вида действий:

1. Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).

2. Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_{i+1} + 1\) копию числа \(a_i\). То есть, возможны следующие преобразования:
   

Иными словами, \(-1\) можно удалить вместе с предыдущим числом, \(0\) можно удалить сам по себе, если он стоит не в начале массива, а \(1\) можно заменить на предшествующее ей число.

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

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(-1 \le a_i \le 1\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

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

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

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

Для каждого 0 <= i < nums1.length найдите индекс j такой, что nums1[i] == nums2[j] и определите следующий больший элемент nums2[j] в nums2. Если следующего большего элемента нет, то ответом на этот запрос будет -1.

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

Входные данные
В первой строке записано натуральное число n - размер массива nums1. Вторая строка содержит n чисел - элементы массива nums1. В третьей строке записано натуральное число m - размер массива nums2. Четвертая строка содержит m чисел - элементы массива nums2.

Ограничения на входные данные

• 1 <= nums1.length <= nums2.length <= 50000
• 0 <= nums1[i], nums2[i] <= 109
• Все числа в массивах nums1 и nums2 уникальны.
• Все числа массива nums1 содержатся в nums2.

a.length - размер массива a

Выходные данные
Выведите ответ на задачу.
 

Примеры

3
4 1 2
4
1 3 4 2

-1 3 -1

2
2 4 
4
1 2 3 4

3 -1

У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p1, p2, ..., pm, где 1<=p1<p2<…<pm<=n, называется хорошей , если spi=ti для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.

Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки s и t таковы, что хотя бы одна хорошая последовательность точно существует.

Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.

Во второй строке входных данных задана строка s, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t, состоящая из строчных букв английского алфавита.

Гарантируется, что существует хотя бы одна хорошая последовательность индексов.

Выведите одно число - максимальную ширину хорошей последовательности.

В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.

Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.

В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.

В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.

Примеры

5 3
abbbc
abc

3

5 2
aaaaa
aa

4

5 5
abcdf
abcdf

1

2 2
ab
ab

1

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных четверок индексов (индексы внутри одной четверки могут совпадать) таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует четверок 1 <= i,j,k,h <= n, для которых выполняется ai+aj+ak+ah=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.

В первом примере не существует четверок с суммой 2022.

Во втором подходят четверки (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2, 1, 2, 1), (2,2,1,1).

В третьем примере подходят все 24 четверки попарно различных индексов. Например, (1,2,3,4) или (4,1,3,2).

Примеры

4
1 1 1 1

0

2
500 511

6

4
129 45 1000 848

24

Примеры

Примеры