Информатика

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

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

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

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

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

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

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

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

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

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

Учитель записывает фактическую длительность каждого проведённого урока в часах и минутах. Стандартная длительность урока — 45 минут. Определите, сколько уроков длились дольше стандартного времени.

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

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

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

Одно число — количество уроков, длившихся строго дольше 45 минут.

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

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

В первой строке подаётся количество совещаний 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\)-му столу, кладет блюдо.

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