Алгоритмы

re.match(pattern, string) - проверяет совпадение ТОЛЬКО в начале строки.

• Возвращает: объект Match или None
• Использование: match = re.match(r'\d+', text)

---

 

Задача: Проверить, что строка начинается с корректного формата лог-записи:

• Дата: ГГГГ-ММ-ДД
• Время: ЧЧ:ММ:СС
• Уровень логирования: INFO, WARN, ERROR, DEBUG

В этой задаче на вход подается одна строка. Вам нужно вывести True если начало строки совпадает с шаблоном и False в противном случае.
 

re.search(pattern, string) - находит ПЕРВОЕ совпадение с шаблоном в строке.

• Возвращает: объект Match или None
• Использование: match = re.search(r'\d+', text)

---

Найти первый товар из категории Electronics и вывести его название и цену в одной строке через пробел. 

Например (только для понимания формата вывода), 
DVD 34.5$

Маша очень любила строить башенки из кубиков в детстве, но теперь она уже взрослая, потому башенки из простых кубиков её не интересуют. Она купила детали для башенки, которые представляют собой блок 3*3*1, который очень легко описать матрицей 3 на 3, так как толщина блока всего 1 кубик.
Маше точно известно, что:

•  при использовании всех блоков, можно гарантированно построить башенку, которая не будет иметь пустот, включая нижнюю и верхнюю границы;
•  используя все блоки, можно построить башенку только одним и не более способами;
•  при строительстве башенки блоки нельзя вращать;
•  только два блока во всём наборе имеют сплошную верхнюю или же нижнюю границу;
•  глубина пустот в блоке может состоять из 1 или 2 элементов;
•  блоков, имеющих пустоты, которые нельзя покрыть при сборе башенки не существует.

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

Входные данные
В первой строке подаётся число N (1 <= N <= 10) – количество блоков для башенки, далее на 3*N строках вводится по 3 цифры через пробел(0 – у блока отсутствует элемент в этой позиции, 1 – сам блок), представляющие из себя N блоков, доступных для строительства.
Нумерация блоков начинается с 1 и увеличивается при описании каждого последующего блока (то есть первый блок, второй и так далее).
Выходные данные
Вывести в ответе в одну строку через пробел каждый элемент – номера блоков в порядке сбора башни снизу-вверх.

Пояснение
Пример №2

 

Компания “РудниК” хочет построить автономный рудодобывающий городок и ей необходимо рассчитать хватит ли её новому городу припасов на автономное существование в течении 100 месяцев. Для автономного существования городу необходимы: токарные изделия, электронные платы, бетон и еда. Изначально в городке находится по 30 единиц каждого ресурса. Каждые 10 месяцев в городок приходит по X единиц каждого ресурса. То есть при наступлении 10-го, 20-го, 30-го месяца и так далее. Чтобы автономно существовать без построек город потребляет по Y единицы каждого ресурса за месяц. Потребление ресурса происходит после поступления ресурсов с заводов и других источников. Если в какой-то месяц один из ресурсов кончится (станет равным 0 или меньше 0), то город закроют, а жителей вывезут. Рудодобывающий город начинает свой отсчёт с дня №1. Администрация города может строить здания, чтобы производить ресурсы самостоятельно:

• - завод по переработке отходов. Стоимость 8 токарных изделий, 3 электронные платы, 10 бетона. Время строительства 5 месяцев. Каждые 2 месяца завод будет выдавать 5 бетона и 2 токарных изделия. Потребляет 3 токарных изделия каждые 5 месяцев. ID завода - 1.
• - теплица. Стоимость 8 бетона и 5 токарных изделий. Время строительства 5 месяцев. Каждые 5 месяцев теплица будет приносить 7 еды. Потребляет 2 бетона каждые 10 месяцев. ID завода - 2.
• - завод по производству электроники. Стоимость 6 электронных плат, 10 токарных изделий, 10 бетона. Время строительства 10 месяцев. Каждые 10 месяцев будет выдавать по 6 электронных плат. Потребляет 2 токарных изделия каждые 18 месяцев. ID завода - 3.
• - завод по производству бетона. Стоимость 4 электронные платы, 8 токарных изделий, 8 бетона. Время строительства 8 месяцев. Каждые 8 месяцев будет выдавать по 8 бетона. Потребляет 1 токарное изделие и 1 электронную плату каждые 12 месяцев. ID завода - 4.

Завод начинает приносить доход или начинает вести отсчёт до выдачи новых ресурсов на следующий месяц после завершения его постройки или прошлой выдачи ресурсов. Если завод приносит ресурсы на n-ый месяц, на следующий n+1 месяц начинается отсчёт прихода ресурсов в новом цикле. Представим, что теплица начнёт строительство в 5-ый месяц, значит её строительство завершится на 9-ый месяц, производить ресурсы она будет с 10-го месяца, а первый “урожай” будет собран на 14-ый месяц. Администрация города может построить несколько заводов, если у неё хватает на это ресурсов. Можно начать строительство завода только, если на момент начала строительства все ресурсы есть в наличии. Месяц начала строительства завода полностью учитывается во времени его строительства. Только разные заводы/строения могут строится одновременно. Эффекты от нескольких заводов складываются.

Формат входных данных
На вход программа получает 2 числа 0<=X<=40, 1<=Y<=40, количество ресурсов, которые колония получается и тратит соответственно. И двумерный массив (каждый элемент на новой строке), размером 4 на 5, указывающий в какой месяц должно начаться строительство того или иного здания. Где по вертикали - ID строения/завода, а по горизонтали номер планируемой к строительству постройки. Каждую постройку могут построить максимально 5 раз. Если в столбце строения указано число 0, значит завод/строение не строится.

Формат выходных данных
На выходе программа должна выдать количество месяцев, которые город смог самостоятельно себя обеспечивать, если он просуществовал 100 месяцев, значит город признан успешным. На следующих строках вывести остаток ресурсов на момент завершения расчётов, не важно успешных или неуспешных. Числа могут принимать отрицательные значения.
Строка 1: Кол-во прожитых месяцев; 2: Токарных изделий; 3: Электронных плат; 4:Бетона; 5:Еды.

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


Укажите схему, соответствующую таблице.

Глеб очень любит компьютерные игры, потому решил впервые разработать свою игру. Он начал с чего-то максимально простого – матричного пинг-понга. Первым этапом Глеб решил сделать алгоритм, который будет считать количество набранных очков мячиком, который будет запускаться в матрице, состоящей из целых чисел.
Для того, чтобы протестировать алгоритм, Глеб указывает стартовую позицию мячика и его стартовое направление (число от 1 до 8). Мячик после прохождения через ячейку матрицы оставляет на её месте дыру, при попадании в будущем в которую игра заканчивается.
Стоит также учесть, что так как это пинг-понг, то мячик отталкивается от стенок, но в данной игре отражение действует по принципу угол отражения равен углу преломления + 45 градусов по часовой стрелке (при попадании в угол мячик отталкивается в обратном направлении + 45 градусов). Если мячик попадает в угол под углом 45 градусов, то он отражается обратно вектору попадания.
Стартовое направление мячика задаётся числом от 1 до 8. Направления представлены в виде матрицы ниже, где x – это текущая позиция мячика.

1	2	3
4	x	5
6	7	8

Входные данные
В первой строке подаются два числа N, M (1 <= N, M <= 100) – размер матрицы, далее на N строках по M целых чисел (от -10000 до 10000) вводится сама матрица. После вводится на одной строке стартовая позиция мячика (нумерация в матрице с 1), а на последней строке вводится стартовое направление мячика (число от 1 до 8).
Выходные данные
Вывести в ответе единственное число – количество набранных очков мячиком после старта.

Примечание
Пример №2: При старте из ячейки -5 по направлению 8 (в правый нижний угол), мячик ударится в угол, значит он должен отразиться в обратном направлении, но так как к углу отражения по правилам игры прибавляется 45 градусов по часовой стрелке, то мячик полетит по направлению не 1 (в левый верхний угол), а по направлению 2 (вверх). Далее отразится в обратном направлении от верхней стенки и попадёт в ячейку -5, на месте которой уже осталась дыра, потому игра окончится.
 

Риэлторская фирма “КвартирКа” решила добавить в своё приложение кредитный калькулятор для своих клиентов. На время тестирования нового обновления калькулятор был сделан более простым.

Формат входных данных
На входе программа получает ряд натуральных целых чисел, разделённых переносом строки: сумма кредита (10000<=x<=999999999), процентная ставка (годовая) ( 1<=x<=100), планируемая сумма для ежемесячного погашения кредита (10000<=x<=999999999).
Формат выходных данных
На выходе программа должна выдать возможно ли выплатить кредит по представленным параметрам в виде: “True” - если возможно, “False” - если невозможно и на следующей строке количество месяцев необходимое для выплаты кредита, если кредит выплатить невозможно следует вывести ноль.

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

Пример: сумма кредита - 50.000, процентная ставка 50%, планируемая сумма погашения 10.000. В первый месяц будут начислены процента на долг, который составит 25.000. В первый месяц вся сумма пойдёт на погашения процентов 25.000-10.000. Во второй месяц, аналогично 15.000-10.000. В третий месяц 5.000 уйдёт на погашение долга по процентам и 5.000 на погашение задолженности, остаётся выплатить 45.000. В четвёртый месяц 45.000-10.000. В пятый 35.000-10.000. В шестой 25.000-10.000. В седьмой 15.000-10.000. На восьмой месяц кредит будет полностью погашен, так как не было набрано 12 месяцев проценты более не начислялись.

Старшеклассник Дима собирает робота, который должен передвигаться по рельсам вокруг испытательного стенда. Всего робот умеет выполнять 12 различных команд, но для нас представляют интерес три из них, связанные с управлением манипулятором. Дима решил передавать роботу блоки инструкций в виде числа: робот получает число, переводит его в систему счисления с основанием 12 и выполняет соответствующие цифрам команды. Коды команд, отвечающих за манипуляторы робота, кратны четырём. На вход подаётся N чисел – блоков с наборами команд. В скольких блоках робот выполнил не менее M команд с манипулятором?

Формат ввода На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество наборов команд. Во второй строке подаётся целое неотрицательное число M (0 ≤ M ≤ 1000) – требуемое количество команд с манипулятором. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*10⁹ – блок команд, записанных в десятичной системе счисления.
Формат вывода Вывести одно целое число – в скольких блоках команд робот выполнил не менее M команд с манипулятором.

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

1. Объем азотной кислоты должен быть не меньше требуемого для работы;
2. Объем азотной кислоты в лаборатории должен быть минимально возможным;
3. При прочих равных следует предпочесть переноску меньшего количества емкостей;

Напишите программу, которая поможет лаборантам.

Формат ввода
В первой строке программы вводится натуральное число N (N ≤ 20) – количество емкостей с кислотой. Во второй строке указывается натуральное число V (0 ≤ V ≤ 200 л) – ограничение по объему. Далее в N строчках вводится по одному натуральному числу v_i (v_i ≤ 20 л) – объем емкости под номером i.
Формат вывода
Вывести в одной строке через пробел в порядке возрастания объемы емкостей, которые надо отнести в лабораторию, уложившись в заданные условия. Если это невозможно, вывести 0.

В ходе игры «Зарница» Витя и Паша пересылают друг другу важные сообщения. Но для того, чтобы противник не смог их понять, сообщения кодируются. Для кодирования информации ребята используют латинский алфавит из 26 букв, все буквы заглавные. Слова кодируются следующим образом. Каждая буква в слове заменяется ее порядковым номером в алфавите, записанном в системе счисления с основанием Sys (2 <= Sys <= 36). Все полученные числа записываются подряд без пробелов. Если числа (порядковые номера букв) в заданной системе счисления могут иметь разную длину, то более короткие числа дополняются слева нулями до требуемой длины. Например, в десятичной системе счисления порядковый номер буквы A будет равен 1, а буквы Z – 26. Соответственно, при шифровании, к единице слева будет дописан ноль. То есть код буквы A будет 01, а код буквы Z – 26. Для усложнения возможной расшифровки сообщения противником, при кодировании разных слов, могут использоваться различные системы счисления. Основание использованной системы счисления, выраженное двухзначным десятичным числом дописывается справа к коду всего слова.
Например, слово AZ, при использовании десятичной системы счисления, будет закодировано как 012610, а при использовании троичной системы счисления будет закодировано как 00122203.

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

Город имеет форму круга радиуса R с центром в точке (0,0).
Сеть метро состоит из N линий метро (часть линий или все проходят через город).
Линия метро - ломаная из отрезков прямых, вершины которых имеют целочисленные координаты. Линия метро не имеет самопересечений и может быть замкнутой. Во всех точках с целочисленными координатами, через которые проходят линии метро расположены станции метро .
Для каждой точки с целочисленными координатами определим параметр вес вершины. Вес вершины — это количество станций метро, расстояние до которых не более 1 (длины клетки).
Город разбит на кварталы. Квартал — это единичная клетка с целочисленными координатами вершин, хотя бы одна из которых находящаяся строго внутри города.
Для каждого квартала определим параметр доступность. Доступность квартала равна сумме весов вершин квартала (вершина квартала может быть вне города)
Найдите значение "доступности" для каждого квартала. Для каждой полученной "доступности" определите число кварталов, имеющих эту доступность.
Входные данные
В первой строке заданы значения R, N (4<R<201, 0<N<1001)
В следующих N строках заданы описания линий метро.
Каждая линия описывается следующим образом:
первое число в строке M равно количеству вершин ломаной, далее даны координаты вершин (по два числа на вершину).
Замкнутые ломаные определяются тем, что координаты начальной и конечной вершины совпадают.
Выходные данные
В первой строке выведите число K - количество различных значений "доступности" (включая нулевую).
В следующих K строках выведите по два числа - значение "доступности" и число кварталов, имеющих такое значение "доступности"

Примеры:

 

 

№	Входные данные	Выходные данные	Примечание
1	5 3 6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4 4 -6 3 0 -1 2 -1 5 -4 3 5 4 0 -1 -6 -4	14 0 3 1 1 2 4 3 8 4 10 5 9 6 12 7 11 8 13 9 5 10 6 11 3 12 2 13 1	Город (рис. 1,2) расположен в круге радиуса 5 с центром в точке (0,0). Сеть метро состоит из 6 линий метро (2 радиальных, 1 кольцевая): 6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4 - кольцевая линия из 5 звеньев, 16 станций 4 -6 3 0 -1 2 -1 5 -4 - радиальная линия из 3 звеньев, 8 станций 3 5 4 0 -1 -6 -4 - радиальная линия из 2 звеньев, 9 станций Есть три пересадки ( в вершинах (-3,1), (0,-1), (3,-2)) На рис.1 отмечены вершины, которые не являются станциями и имеют не нулевой вес (треугольник - вес 1, крестик - вес 2, ромб - вес 3) На рис.2 для всех городских кварталов указано значение параметра доступности квартала.

 

В ходе игры «Зарница» Саша и Женя пересылают друг другу важные сообщения. Но для того, чтобы противник не смог их понять, сообщения кодируются. Для кодирования информации ребята используют латинский алфавит из 26 букв, все буквы заглавные. Слова кодируются следующим образом. Каждая буква в слове заменяется ее порядковым номером в алфавите, записанном в системе счисления с основанием Sys (2 <= Sys <= 36). Все полученные числа записываются подряд без пробелов. Если числа (порядковые номера букв) в заданной системе счисления могут иметь разную длину, то более короткие числа дополняются слева нулями до требуемой длины. Например, в десятичной системе счисления порядковый номер буквы A будет равен 1, а буквы Z – 26. Соответственно, при шифровании, к единице слева будет дописан ноль. То есть код буквы A будет 01, а код буквы Z – 26. Для усложнения возможной расшифровки сообщения противником, для кодирования букв, стоящих на разных местах в слове, используются различные системы счисления. Основание использованной системы счисления выбирается исходя из порядкового номера буквы в кодируемом сообщении. Для кодирования первой буквы сообщения используется двоичная система счисления, для второй – троичная, для третьей – четверичная и т.д., до системы счисления с основанием 36 включительно. Далее основания систем счисления повторяются циклически – 2, 3, 4, …36, 2, 3, … Например, слово AZ, будет закодировано как 00001222.
Напишите программу, которая будет расшифровывать закодированные сообщения.
На вход программе подается одно закодированное сообщение. Длина сообщения не более 200 символов. Программа должна вывести исходное слово.

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

Формат ввода
На вход программе в первой строке подается натуральное число N, не превышающее 10000 – количество замеров температуры.
Во второй строке подается натуральное число X, не превышающее 1000 – пороговое значение температуры.
Далее в N строках подается по одному натуральному числу t_i, не превышающему 1000 – температура смеси при измерении номер i.
Формат вывода
Вывести одно целое число – сколько минут длился самый длительный нагрев смеси.

Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Формат ввода
На вход программе в первой строке подаётся натуральное число N. Далее идет N строк, каждая из которых содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
   0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
   1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
   2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
   3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Формат вывода
T строк: первая строка - состояние точки K в первую мс, вторая строка - состояние точки K во вторую мс, и так далее до T мс.

Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.

Старшеклассник Миша собирает робота, который должен передвигаться по рельсам вокруг испытательного стенда. Всего робот умеет выполнять 13 различных команд, но для нас представляют интерес три из них – «вперёд», «назад», «стой». Миша решил передавать роботу инструкции в виде цифр числа: робот получает число, переводит его в систему счисления с основанием 13 и выполняет соответствующие цифрам команды. Коды команд, отвечающих за изменение скорости робота, кратны шести.
На вход подаётся N чисел с наборами команд. Сколько раз робот изменит скорость, если считать, что он не встречает препятствий?

Формат ввода
На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество наборов команд. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*109 – набор тринадцатеричных команд, записанных в десятичной системе счисления.
Формат вывода
Вывести одно целое число – сколько раз робот изменит скорость.

На уроке информатики Фоме задали задачу о проверке гипотезы Гольдбаха.
Условие задачи выглядело так:
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Фома легко решил данную задачу методом поиска "первого решения".
Дома, Фома заметил, что во время отладки, он получал решения, в которых одно из чисел было не очень большим.
Так, для числа 1000000, он получил разложение 1000000=17+999983. Фома решил проверить, в чем сложность гипотезы Гольдбаха.
Для этого Фома придумал задачу:
Определим функцию g(n) = количеству разложений числа n в сумму двух простых чисел. (разложения, отличающиеся порядком слагаемых, считаются одинаковыми).
На отрезке натуральных чисел от A до B найдите чётное число x такое, что: g(x) кратно 5 и имеет минимальное значение среди всех g(x) кратных 5 на этом отрезке.
Решите задачу Фомы.

Входные данные
Границы отрезка A, B (два натуральных числа 5≤ A<B≤106 )
Выходные данные
- "Impossible" если для всех чётных x из отрезка [A;B] значение g(x) не кратно 5.
- два числа - x, g( x ) ( g(x) кратно 5 и минимальное для A≤ x≤B). Если таких x несколько, то выведите минимальное значение x.

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 10	Impossible	На отрезке всего три четных числа (6, 8, 10) Число 8 =3+5 и других представлений нет (5+3 считается таким же как 3+5) Для 10 есть два представления (3+7 и 5+5) Таким образом значений x, при которых g(x) кратно 5 нет.
2	20 60	48 5	g(x) может принимать значения меньшие 3 (g(20)=2) g(x)=5 для x из множества {48, 54}. 48 -минимальное значение
3	2000 2005	Impossible

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

Аспирант Шлёпов собирается провести чемпионат вуза по шахматам. Так как игроков в вузе много, у сообщества есть свой рейтинг ELO. Шлёпов собирается разделить игроков на основании этого рейтинга на две лиги. В высшей лиге должно играть не менее трети игроков, но при этом наименьшее возможное количество; отбор в лигу идёт на основании ELO. Двух игроков с одинаковым ELO распределять в разные лиги нельзя. Высшая лига на турнире должна быть обязательно. Определите, начиная с какого ELO, игроки попадают в высшую лигу.

Формат входных данных
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество игроков. Далее в N строках идёт по одному натуральному числу k_i – рейтинг ELO игрока номер i (1 ≤ k_i ≤ 2500).
Формат выходных данных
Выведите одно целое число – ELO, начиная с которого, игроки попадают в высшую лигу. Если в высшей лиге окажется весь турнир, надо вывести наименьший ELO среди заявленных игроков.

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

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

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

Замок на двери подвала устроен следующим образом:

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(a\), а второй — на число \(b\);

• первый кодовый механизм сломан, поэтому изменить значение \(a\) нельзя;

• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение \(b\);

• замок открывается тогда и только тогда, когда существует целое число \(d > 1\), делящее и \(a\), и \(b\) (иными словами, когда у \(a\) и \(b\) есть общий делитель больше единицы).

За одну секунду Эрен может повернуть второй кодовый механизм так, что \(b\) увеличится ровно на \(1\). Определите, за какое минимальное время Эрен сможет открыть подвал.

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

В \(i\)-й из следующих \(t\) строк через пробел даны два целых числа \(a_i\) и \(b_i\) — начальные значения, на которые указывают кодовые механизмы в \(i\)-м тесте (\(2 \leqslant a_i, b_i \leqslant 10^9\)).

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