Алгоритмы

Пользователь вводит количество учеников, а затем для каждого — имя и оценку. Сохраните данные в словарь. Выведите пары в формате Имя — оценка, отсортированные по оценке в порядке убывания. Если оценки одинаковые, сохраните порядок ввода.

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

Первая строка — целое число \(N\) (\(1 \le N \le 10\)).

Следующие \(N\) строк — имя и оценка (целое число) через пробел. Имена уникальны.

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

\(N\) строк в формате Имя — оценка, отсортированные по убыванию оценки.

Пользователь вводит количество учеников, а затем для каждого — имя и оценку. Сохраните данные в словарь. Выведите пары в формате Имя — оценка, отсортированные по имени в алфавитном порядке.

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

Первая строка — целое число \(N\) (\(1 \le N \le 10\)).

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

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

\(N\) строк в формате Имя — оценка, отсортированные по имени (алфавитный порядок).

В расписании записаны моменты начала каждого урока (часы и минуты). Уроки идут в хронологическом порядке. Перерывом считается промежуток между концом одного урока и началом следующего. Каждый урок длится ровно 45 минут. Определите количество перерывов длительностью более 30 минут.

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

Каждая строка содержит два целых числа: часы и минуты начала урока (0 ≤ часы ≤ 20, 0 ≤ минуты ≤ 59). Последовательность заканчивается строкой «0 0». Она не является временем урока. Гарантируется, что уроков не менее двух.

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

Одно число — количество перерывов длительностью строго более 30 минут.

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

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

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\)).

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

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

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

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 2^𝑛 навыков, пронумерованных 1 до 𝑑. Эти навыки расположены на листьях полного двоичного дерева высоты 𝑛, изначально все навыки имеют уровень 1. Пример такого дерева для 𝑛 = 3 приведен на иллюстрации ниже.



После этого вы начинаете прокачивать навыки следующим образом.
• Навыки прокачиваются посредством заполнения двоичного дерева снизу вверх.
• Для очередной вершины дерева вы должны выбрать и записать в нее один из двух навыков, записанных в
непосредственных детях этой вершины (на рисунке из детей в родителя ведут стрелки).
• Уровнем навыка считается число вершин, в которых выбран этот навык.
Пример корректного распределения навыков по дереву для 𝑛 = 3 приведен ниже.


В этом примере первый навык имеет уровень 4, седьмой – уровень 3, четвертый и пятый – уровень 2, а второй, третий, шестой и восьмой не были прокачаны ни разу, поэтому остались на уровне 1.
Кроме прокачки персонажа, в игре есть 𝑚 различных квестов, с помощью которых можно получать монетки. Квесты активируются после того, как все дерево навыков было заполнено.
Квесты бывают трех типов:
1. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго меньше 𝑘𝑖 .
2. «𝑒𝑥𝑎𝑐𝑡 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется равен 𝑘𝑖 .
3. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго больше 𝑘𝑖 .
Так как монеты – очень ценный ресурс в игре «Бинарная Сила», вы хотите узнать максимальное количество монет, которое возможно получить с помощью имеющихся квестов после улучшения всех навыков.

Формат входных данных
Каждый тест состоит из нескольких независимых наборов входных данных. Первая строка содержит одно целое число 𝑡 – количество наборов входных данных (1 ≤ 𝑡 ≤ 10⁴). Далее следует описание наборов входных данных.
Каждый набор начинается со строки, содержащей два целых числа 𝑛 и 𝑚 – высоту дерева навыков и количество квестов соответственно (1 ≤ 𝑛 ≤ 15; 0 ≤ 𝑚 ≤ 50 000). Число навыков при этом равно 𝑑 = 2^𝑛.
Далее следуют 𝑚 строк, 𝑖-я из которых содержит четыре целых числа 𝑡𝑖, 𝑥𝑖, 𝑘𝑖, 𝑠𝑖 – тип квеста и его описание (1 ≤ 𝑡𝑖 ≤ 3; 1 ≤ 𝑥𝑖 ≤ 𝑑; 1 ≤ 𝑘𝑖 ≤ 𝑛; 1 ≤ 𝑠𝑖 ≤ 10⁹). Типы квестов следуют в том же порядке, в котором они перечислены в условии: 𝑡𝑖=1 соответствует квесту типа «𝑙𝑒𝑠𝑠», 𝑡𝑖 = 2 – квесту типа «𝑒𝑥𝑎𝑐𝑡» и 𝑡𝑖 = 3 – квесту типа «𝑚𝑜𝑟𝑒».
Гарантируется, что сумма 𝑑 по всем наборам входных данных не превосходит 2¹⁶ и сумма 𝑚 по всем наборам входных данных не превосходит 50 000

Формат выходных данных
Для каждого набора выходных данных в отдельной строке выведите единственное число – максимальное количество монет, которые можно заработать.
 

Известный завод ждет реорганизация — его собираются переоборудовать 𝑛 новейшими станками. Перед тем, как эти станки будут установлены, требуется разработать интерфейс для обработки задач на этих станках.
После реорганизации наладчик завода будет распределять поступающие задачи между станками. У каждой задачи есть длительность. У каждого станка есть независимая очередь задач, причем новую задачу можно добавить либо строго в конец этой очереди, либо строго в начало, если это срочная задача.
Станки работают строго в порядке очереди, обрабатывая задачи подряд. Как только станок завершает задачу, он сразу же начинает работу над следующей в очереди, если такая есть. На переключение между задачами время не тратится.
Формально определим время начала работы над задачей как первый момент времени, после которого прогресс по задаче строго увеличится. Так, если в момент времени 𝑡 на свободный станок приходят сначала обычная задача 𝐴 и затем срочная задача 𝑈, временем начала 𝑈 станет 𝑡, а временем начала 𝐴 — момент завершения 𝑈.
Аналогично, время завершения работы над задачей — первый момент времени, когда прогресс по задаче достигает ее длительности. Так, если в момент времени 𝑡 прогресс по задаче 𝐴 достиг ее длительности, и станку поступил запрос на обработку срочной задачи 𝑈, временем завершения 𝐴 все равно будет 𝑡.
Для большего понимания советуем после прочтения условия ознакомиться с иллюстрацией внизу.
Всего поддерживается четыре типа запросов.

1. Добавить задачу номер 𝑖 длительностью 𝑑 в конец очереди 𝑘-го станка.
   Если его очередь до этого была пустой, станок тут же начинает работу над добавленной задачей
2. Отменить задачу с номером 𝑖. Если эта задача еще не была начата, она удаляется из очереди, а порядок остальных задач в очереди не меняется. Если эта задача уже была начата, работа над ней тут же останавливается, и станок берет в работу следующую задачу из очереди. Если эта задача уже была завершена или такой задачи не было, запрос отмены игнорируется
3. Добавить срочную задачу с номером 𝑖 длительностью 𝑑 в начало очереди 𝑘-го станка. В этом случае работа над текущей задачей (если она есть) на 𝑘 -м станке приостанавливается с сохранением прогресса, и в работу берется данная срочная задача.
   До момента завершения срочной задачи все запросы добавления или отмены новых задач к станку номер 𝑘 игнорируются для экономии ресурсов. Иными словами, если в момент времени 𝑡 поступил запрос добавления срочной задачи, все следующие запросы, поступающие к 𝑘-му станку в моменты времени с 𝑡 включительно до 𝑡 + 𝑑 не включительно будут проигнорированы.
   По завершении срочной задачи, если работа над какой-то обычной задачей в очереди была приостановлена, эта задача без задержек возвращается в обработку.
4. Вывести ожидаемый момент времени завершения работы 𝑘-го станка.
   Для станка без задач в очереди «ожидаемым» временем завершения его работы будем считать текущий момент времени.

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


Формат входных данных
В первой строке дано целое число 𝑇 (1 ≤ 𝑇 ≤ 1000) — количество наборов входных данных. В первой строке описания набора входных данных через пробел даны два целых числа 𝑛 и 𝑞 (1 ≤ 𝑛, 𝑞 ≤ 10⁵) —
количество станков и количество запросов. Гарантируется, что сумма 𝑛 и сумма 𝑞 по всем наборам входных данных обе не превосходят 10⁵.
В следующих 𝑞 строках описаны запросы к заводу в одном из следующих форматов:
1. «𝑡 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить задачу на 𝑘-й станок;
2. «𝑡 𝑐𝑎𝑛𝑐𝑒𝑙 𝑖» — отменить задачу;
3. «𝑡 𝑢𝑟𝑔𝑒𝑛𝑡 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить срочную задачу на 𝑘-м станке;
4. «𝑡 𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛 𝑘» — узнать текущее ожидаемое время завершения работы 𝑘-го станка.
Параметр 𝑡 — момент совершения запроса (целое неотрицательное число от 0 до 10⁹). Для всех запросов выполняется 1 ≤ 𝑘 ≤ 𝑛, 1 ≤ 𝑖 ≤ 109 и 1 ≤ 𝑑 ≤ 10⁹.
Также гарантируется, что номера задач (𝑖) уникальны и не повторяются, а запросы упорядочены по времени, то есть 𝑡 каждого следующего запроса не меньше, чем 𝑡 предыдущего.


Формат выходных данных
Выведите в отдельной строке текущее ожидаемое время работы соответствующего станка после каждого запроса типа «𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛».
Затем выведите по строке на каждую задачу, запрос на добавление которой не был проигнорирован. Задачи должны быть упорядочены по возрастанию их номеров. В каждой строке через пробел должны быть выведены три числа: номер задачи, время начала ее обработки и время конца ее обработки (или отмены, если задача была отменена до завершения).
Для задач, которые были отменены до начала работы над ними, считайте время начала равным времени первого запроса их отмены.



Замечание
В первом примере из условия обе задачи будут обработаны по расписанию: с 0 до 10 и с 4 до 7 соответственно.
Во втором примере:
1. первая задача должна обрабатываться на первом станке в период [0, 5];
2. вторая задача должна обрабатываться на втором станке в период [0, 5];
3. в момент времени 2 срочная задача номер 3 добавляется на первый станок; она будет обрабатываться в период [2, 7];
4. в момент времени 6 первому станку нужно еще 4 единицы времени на завершение задач 4 и 1; второй станок завершил работу в момент времени 5, а третий станок вообще не начинал работу — для них время ожидания до завершения работы равно 0.

Подробная иллюстрация к третьему примеру приведена ниже. Здесь синим обозначен прогресс по задачам, зеленым — завершенные задачи, красным — отмененные, а градиентом — срочные. Все интервалы короче 1 единицы времени (см. отмененную задачу 3) стоит воспринимать как интервалы длительностью 0.





 

Рассмотрим натуральное число \(x\). Требуется прибавить к нему минимальное возможное целое неотрицательное число \(y\), чтобы двоичная запись получившегося числа \(x+y\) имела ровно \(k\) единиц.

Формат входных данных
Первая строка ввода содержит натуральное число \(x\) (\(1 \le x \le 10^{18}\)).

Вторая строка ввода содержит натуральное число \(k\) (\(1 \le k \le 60\)).

Формат выходных данных
Выведите минимальное возможное целое неотрицательное число \(y\), такое что двоичная запись числа \(x+y\) имеет ровно \(k\) единиц.

Постулат Бертрана утверждает, что для любого \(n \ge 2\) найдётся простое число \(p\), для которого \(n < p < 2n\). Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном, проверившим её до \(n = 3\,000\,000\), и доказан в 1852 году Чебышёвым.

Петя хочет повторить подвиг Бертрана и убедиться в справедливости его постулата для разных значений \(n\). Однако, поскольку он не сомневается в корректности доказательства Чебышёва, он немного изменил цель: для данного \(n\), Петя хочет найти максимальный по длине отрезок составных чисел, который лежит строго между \(n\) и \(2n\).

Требуется найти такие \(l\) и \(r\), чтобы \(n < l \le r < 2n\), все числа от \(l\) до \(r\), включительно, были составными и \(r - l\) было максимально. Если подходящих отрезков несколько, необходимо вывести тот, у которого \(l\) минимально.

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

Формат выходных данных
Выведите искомые \(l\) и \(r\).