Информатика

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

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

В первой строке подаётся количество совещаний N. В каждой из следующих N строк — два целых числа: часы и минуты длительности одного совещания (0 ≤ часы ≤ 8, 0 ≤ минуты ≤ 59).

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

Два числа через пробел — длительность самого длинного совещания в часах и минутах.

Оператор связи фиксирует длительность каждого телефонного разговора в часах и минутах. Определите суммарную длительность всех разговоров.

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

В первой строке подаётся количество звонков N. В каждой из следующих N строк — два целых числа: часы и минуты длительности одного звонка (0 ≤ часы ≤ 10, 0 ≤ минуты ≤ 59).

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

Два числа через пробел — суммарное время в часах и минутах.

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

Многолетние исследования показали следующие примечательные черты Мурмурградска:

1. Дома и котодорожки представляют собой дерево, где дома — вершины, а котодорожки — ребра.

2. Между двумя домами есть котодорожка тогда и только тогда, когда котики в этих домах дружат.

Кошачий мэр решил, что для развития общей сплоченности каким-то котикам нужно будет поменять место жительства. При этом мэру важно, чтобы у всех оставалось свое личное пространство, поэтому никакие два котика не должны жить в одном доме после переезда. Мэр также понял, что, во избежание всеобщего хаоса, надо добавить в план немного стабильности: жители домика номер \(1\) должны остаться на месте.

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

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

Так как это число может быть очень большим, необходимо посчитать его по модулю \(998244353\).

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

Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит одно целое число \(n\) — количество вершин в дереве. Далее идут \(n - 1\) строк, каждая содержит два целых числа \(u\) и \(v\) (\(1 \leq u, v \leq n\), \(u \neq v\)) — две вершины, которые соединены ребром.

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

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

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

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

Формат ввода

В первой строке задается количество наборов входных данных T. В этой задаче T всегда равно 1.

В первой строке каждого описания набора дано два целых числа m и k ( 1≤m≤3, 1≤k≤13 ) — число различных типов клавиш и требуемая длина различных подстрок.

В следующих m строках описываются клавиши. Каждое описание состоит из маленькой английской буквы C_i​, написанной на клавише, и числа T_i​ — количества таких клавиш. Гарантируется, что суммарное количество клавиш не превосходит 16.

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

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

Вася открыл собственный классифайд (доску объявлений). Устроен его классифайд следующим образом: для каждого типа товара продавец с номером \(i\) может выставить на продажу только одну единицу товара и заранее указывает минимальную цену \(S_i\), за которую он готов его продать. Каждый покупатель может купить только одну единицу товара, покупатель с номером \(j\) указывает максимальную цену \(B_j\), за которую он готов купить товар. Раз в день Вася собирает все заявки и распределяет покупателей и продавцов, которые заключат сделку и по какой цене. При этом сделка между продавцом \(i\) и покупателем \(j\) может состояться только если \(S_i \le B_j\) по любой цене от \(S_i\) до \(B_j\) (цену назначает Вася).

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

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

В первой строке описания каждого набора записано число \(N\) (\(1 \le N \le 10\)) — количество продавцов.

В следующей строке записано \(N\) чисел \(S_i\) (\(1 \le S_i \le 100\)).

В следующей строке записано число \(M\) (\(1 \le M \le 10\)).

В следующей строке записано \(M\) чисел \(B_i\) (\(1 \le B_i \le 100\)).

Описания наборов отделяются друг от друга пустой строкой.

Формат выходных данных
Для каждого набора входных данных выведите одно число — максимальную суммарную стоимость проданных товаров.

В этой задаче на проверку необходимо сдать исходный код программы.

Дана строка, задающая полином \(f(x)\) степени не выше 3, и два целых числа \(a\), \(b\) — пределы интегрирования. Выполните три операции:

1. Найдите производную \(f'(x)\) и упростите её.

2. Вычислите определённый интеграл \(\displaystyle\int_a^b f(x)\,dx\). Выведите точное значение (целое или дробное, например 27/4 или 0).

3. Найдите все вещественные корни \(f(x) = 0\). Выведите их через пробел в порядке возрастания. Если вещественных корней нет — выведите none. Кратные корни выводятся один раз.

Формат ввода.
Строка 1: выражение полинома в синтаксисе Python (** для возведения в степень, * для умножения, только переменная x).
Строка 2: два целых числа \(a\) и \(b\) через пробел (\(-100 \le a < b \le 100\)).

Формат вывода. Ровно 3 строки:

derivative: <выражение>
integral: <точное значение>
roots: <числа через пробел, или "none">

Пример ввода 1:

x**3 - 4*x**2 + x + 6
0 3

Пример вывода 1:

derivative: 3*x**2 - 8*x + 1
integral: 27/4
roots: -1 2 3

Пример ввода 2:

x**2 - 4*x + 4
0 3

Пример вывода 2:

derivative: 2*x - 4
integral: 3
roots: 2

Корень \(x=2\) кратный — выводим один раз.

Разбор примера 1. \(f(x) = x^3 - 4x^2 + x + 6\).

\[f'(x) = 3x^2 - 8x + 1, \qquad \int_0^3 f\,dx = \left[\frac{x^4}{4} - \frac{4x^3}{3} + \frac{x^2}{2} + 6x\right]_0^3 = \frac{81}{4} - 36 + \frac{9}{2} + 18 = \frac{27}{4}\] \[f(-1) = -1-4-1+6 = 0,\quad f(2) = 8-16+2+6=0,\quad f(3)=27-36+3+6=0.\] Корни: \(-1,\ 2,\ 3\).

Подсказки по реализации.

• Для разбора строки: parse_expr(s, transformations=standard_transformations + (implicit_multiplication_application,)).

• Чтобы отфильтровать только вещественные корни: im(r) == 0.

• simplify(diff(expr, x)) даёт упрощённый вид производной.

• Сортировка корней: sorted(..., key=lambda r: float(r)).

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

Формат ввода (CSV, stdin). Первая строка — заголовок: name,math,physics,informatics,english Далее строки с данными (\(2 \le n \le 1000\)).

Формат вывода. По одному имени на строке (лексикографический порядок).

Пример ввода:

name,math,physics,informatics,english
Alice,90,85,95,80
Bob,60,55,65,50
Charlie,75,80,70,85
Diana,40,45,35,50

Пример вывода:

Alice
Charlie

Общее среднее \(\approx 66.25\).

Условие. Дана матрица \(A\) размера \(n \times m\). Вычислите суммы по строкам \(r_i = \sum_{j} a_{ij}\) и суммы по столбцам \(c_j = \sum_{i} a_{ij}\).

Формат ввода. Первая строка: \(n\) и \(m\) (\(1 \le n, m \le 500\)). Следующие \(n\) строк по \(m\) целых чисел.

Формат вывода. Строка 1: \(n\) чисел — суммы по строкам. Строка 2: \(m\) чисел — суммы по столбцам.

Пример ввода:

3 3
1 2 3
4 5 6
7 8 9

Пример вывода:

6 15 24
12 15 18

Условие. Дан массив из \(n\) чисел и размер окна \(k\). Вычислите скользящий максимум: \(M_i = \max(a_i, a_{i+1}, \ldots, a_{i+k-1}), \quad i = 0, 1, \ldots, n-k.\) 

Формат ввода. Первая строка: два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 10^5\)). Вторая строка: \(n\) целых чисел (\(-10^9 \le a_i \le 10^9\)).

Формат вывода. Одна строка: \(n - k + 1\) целых чисел, разделённых пробелами.

Пример ввода:

7 3
2 1 5 3 6 4 8

Пример вывода:

5 5 6 6 8

Условие. Дан массив из \(n\) вещественных чисел. Вычислите и выведите пять статистических характеристик.

Формат ввода. Первая строка содержит целое число \(n\) (\(1 \le n \le 10^5\)). Вторая строка содержит \(n\) вещественных чисел, разделённых пробелами.

Формат вывода. Пять строк, каждая в виде <метка>: <значение>, значение округлено до 4 знаков после запятой:\(\bar{a} = \frac{1}{n}\sum_{i=1}^{n} a_i, \qquad \sigma(a) = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(a_i - \bar{a})^2}\)  

Пример ввода:

5
3.0 1.0 4.0 1.0 5.0

Пример вывода:

min: 1.0000
max: 5.0000
mean: 2.8000
median: 3.0000
std: 1.6000

Так как стандартная операция сложения слишком сложна, чтобы описать её в рамках этой страницы, мы введём свою операцию сложения <<+>>. Результатом сложения чисел \(A\) и \(B\) (обозначим \(A+B\)) назовём число, полученное приписыванием справа к \(A\) числа \(B\). Например \(20 + 25 = 2025\), а \(25 + 20 = 2520\). Как видите, \(A + B\) не всегда равно \(B + A\), так что найдите большее из них.

То есть по заданным \(A\) и \(B\) требуется найти наибольшее из чисел \(A+B\) и \(B+A\).

В единственной строке вводятся два целых числа \(A\) и \(B\) (\(0 < A, B < 1000\)).

Выведите единственное число — наибольшее из чисел \(A+B\) и \(B+A\).

Недавно директору Ресторана Отеля пришла в голову следующая мысль: <<Все какое-то обычное. Надо что-то модернизировать!>> Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.

Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО <<В Гараже у Петровича>>. И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили \(n\) столов и приготовили \(n\) блюд. Все блюда попарно различны и имеют номера от \(1\) до \(n\). Изначально, блюда по мере готовности как-то расставили по \(n\) столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, \(i\)-е блюдо должно оказаться на \(i\)-м столе.

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

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

Формат входных данных
В первой строке записано одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество столиков в Ресторане.

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

Формат выходных данных
Выведите <<YES>>, если робоанты смогут расставить все блюда по местам, и <<NO>> в противном случае случае.

Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:

1. Берёт со \(2\)-го стола \(8\)-е блюдо, перемещается к \(8\)-му столу, кладет блюдо.

2. Берёт с \(8\)-го стола \(2\)-е блюдо, перемещается ко \(2\)-му столу, кладет блюдо.

3. Перемещается к \(4\)-му столу.

4. Берёт с \(4\)-го стола \(6\)-е блюдо, перемещается к \(6\)-му столу, кладет блюдо.

5. Берёт с \(6\)-го стола \(4\)-е блюдо, перемещается к \(4\)-му столу, кладет блюдо.

Можно доказать, что во втором примере невозможно расставить все блюда по местам.

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

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

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

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

Формат входных данных
Первая строка содержит одно целое число \(n\) \((1 \le n \le 10^6)\) — количество котиков.

Вторая строка содержит \(n\) целых чисел \((1 \le a_i \le 10^6)\), где \(a_i\) — милота \(i\)-го котика.

Третья строка содержит одно число \(m\) \((0 \le m < n)\) — количество котиков, толкающих своего соседа.

Каждая из последующих \(m\) строк содержит два числа \(k_i\) \((1 \le k_i < n)\) и \(q_{k_i}\) \((1 \le q_{k_i} \le 10^6)\), обозначающую, что если \(k_i\) котик толкается, то общая милота ужина уменьшается на \(q_{k_i}\).

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

В первом примере можно отсадить первого питомца к общей миске, а остальных отправить ужинать за свои миски. Суммарная милота благодаря тому, что котики кушают за своими мисками, будет равна \(20 + 30 + 40 + 50 = 140\), но третий котик будет толкать четвертого, поэтому из этой суммы вычитается \(q_3 = 25\). Таким образом, ответ на этот пример равен \(115\).

Вы с друзьями устроили марафон просмотра фильмов про отели, проголодались и решили заказать пиццу. Пока вы выбирали, с какого фильма начать просмотр, курьер с пиццей уже почти приехал. Вам пришло уведомление, что <<Курьер уже почти на месте>>, но прошло уже 5 минут, а пицца всё ещё не доставлена. Что же случилось?

Курьер действительно приехал по нужному адресу, но не может понять, действительно ли это тот отель, в который заказали пиццу. Вывеска отеля представляет из себя прямоугольник, состоящий из \(n\) строк по \(m\) заглавных латинских букв в каждой. И курьер не имеет ни малейшего понятия, где на ней написано название отеля.

Курьер попросил помощи у прохожего, на что тот ответил, что не помнит, как называется отель, зато знает, как найти название на вывеске. Он рассказал, что ещё совсем недавно у курьера не возникло бы проблем: на вывеске было только слово <<HOTEL>> и название отеля (также состоящее из 5 букв). Название начинается с буквы <<L>>, поэтому хозяин решил оформить вывеску так: он написал слово <<HOTEL>> так, чтобы соседние буквы граничили по стороне, а после этого так же (с тем же расположением букв относительно предыдущих) написал название, начав его с последней буквы слова <<HOTEL>>. Для лучшего понимания посмотрите, как могла бы выглядеть вывеска отеля с названием LUCKY:

Хозяину отеля так понравилось рисовать буквы, что он решил заполнить ими вообще все клетки матрицы-вывески. Чтобы у посетителя остался шанс найти название, хозяин вписал буквы так, чтобы ни в каком другом месте нельзя было прочитать слово <<HOTEL>>.

Зная всю эту информацию, курьер смог выяснить название отеля. А сможете ли вы?

Формат входных данных
В первой строке даны два числа \(n\) и \(m\) \((1 \le n, m \le 100)\) — размеры вывески.

В следующих \(n\) строках дана сама матрица-вывеска. Каждая из строк состоит из \(m\) заглавных букв латинского алфавита.

Гарантируется, что слово <<HOTEL>> встречается в матрице ровно один раз.

Формат входных данных
Выведите единственное слово из пяти заглавных латинских букв — название отеля.

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

В Отеле ключ открывает комнату, только если выполнено следующее условие. Для каждого \(1 \le i < n\), сумма \(i\)-й и \((i+1)\)-й цифры номера комнаты должна быть равна \(i\)-й цифре ключа по модулю 10. Помимо этого, последняя цифра ключа должна быть равна сумма первой и последней цифры номера комнаты по модулю 10.

Найдите все номера комнат, которые открывает имеющийся у Вас ключ.

Формат входных данных
На первой строке дано число \(n\) (\(2 \le n \le 100\,000\)) — количество цифр в номерах комнат.

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

Формат выходных данных
На первой строке выведите количество комнат, открываемых ключом.

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

Поясним второй пример. Ключ с номером 25575 открывает комнату 57870 так как: \[2 = (5 + 7) \mod 10\] \[5 = (7 + 8) \mod 10\] \[5 = (8 + 7) \mod 10\] \[7 = (7 + 0) \mod 10\] \[5 = (0 + 5) \mod 10\]

Можно проверить аналогичные равенства и для комнаты 02325. Утверждается, что больше никакие комнаты этим ключом открыть нельзя.