Структуры данных

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

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

Поэтому он просит вас помочь ему: выберите из n наборов карандашей ровно k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше.

Формат входного файла
В первой строке находятся два натуральных числа n, k (1 ≤ n ≤ 10⁵ , 1 ≤ k ≤ n) — количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку. В каждой из следующих n строк находится ci (1 ≤ ci ≤ 2·10⁵ ) — количество карандашей в наборе. Далее, в этой же строке, следуют ci натуральных чисел aij (1 ≤ a_ij ≤ 10⁹ ) — длины карандашей в i-м наборе. Гарантируется, что сумма всех c_i не превосходит 2 · 10⁵ .

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

Ввод	Вывод
3 2 3 1 3 4 3 5 1 2 1 4	3
5 3 3 2 1 3 2 4 1 3 4 2 4 4 3 2 3 3 2 5 6	3

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

Недавно вышла новая игра Counter-Strike 2. В 5-м классе учится N человек, и все они хотят поиграть в эту игру. На уроке физкультуры всех учеников построили в шеренгу. У физрука Олега Евгеньевича сегодня смешанное настроение: он решил разрешить ученикам поиграть в CS2 вместо физических занятий, но играть они будут только по определенным правилам. 

Олег Евгеньевич будет разрешать играть всем ученикам, номер в шеренге которых лежит в отрезке \([L;R]\). Олег Евгеньевич узнал, что родители детей разрешают играть им в компьютер только ti минут. Но ученики очень любят компьютерные игры, поэтому каждый будет играть ровно ti минут, при этом играть никто не отказывается. 

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

Например, играют 2 игрока. Если у играющего 1 время \(t_1 = 12\), а у играющего 2 время \(t_2 = 8\), то максимально возможное время матча 4 минуты. 1 играющий сможет сыграть 3 матча по 4 минуты, а 2 – 2 матча по 4 минуты. 

Олег Евгеньевич в последнее время усердно занимается математикой, поэтому он решил M раз посчитать максимальное время Q для играющих от L до R. Вам следует проверить Олега Евгеньевича. Для этого следует вывести YES, если он прав, иначе – NO.

Входные данные
Первая строка содержит число N (\(1 <= N <= 10000\)) – количество ребят. Во второй строке записаны N чисел – ti (\(1 <= t_i <= 1000\)), время, которое дают родители i-ому ребенку на игру. В третьей строке записано число M (\(1 <= M <= 10^8\)), количество запросов. Далее, в M строках идут 3 числа L, R, Q (время, которое посчитал Олег Евгеньевич).

Выходные данные
Выведите для каждого запроса YES, если Олег Евгеньевич правильно посчитал, иначе – NO.

 

Примеры

№	Входные данные	Выходные данные
1	3 8 5 6 4 1 2 2 1 3 1 2 3 1 1 3 2	NO YES YES NO

Вам дан массив A [1…N]. Требуется выполнить M операций вычисления минимального элемента на отрезке с L по R.

Входные данные
Первая строка содержит число N (\(1 <= N <= 100000\)) – размер массива. Во второй строке записаны N чисел – элементы массива. Третья строка содержит число M (\(1 <= M <= 100000\)) – количество запросов минимума. Следующие M строк содержат пары чисел L и R (\(L <= R <= N\)), описывающие отрезки.

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

 

Примеры

№	Входные данные	Выходные данные
1	5 3 1 8 7 9 2 1 3 3 5	1 7

Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_i минут.

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

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

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

Ввод	Вывод
1 2 5 6 3 5	12
3 1 15 10 1 3 4 5 30 35	105

Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку

Улица М. города Д. печально известна среди местных жителей качеством дорожного покрытия. В этом тяжело винить ремонтные службы: пожалуй, они следят за этой улицей даже слишком тща- тельно. Проблема в том, что каждый без исключения ремонт улицы выглядит следующим образом: бригада рабочих выбирает некоторый участок улицы единичной длины и меняет асфальт только на нём, причём тип асфальта на этом участке в результате может отличаться от типов асфальта на других участках, что, разумеется, усложняет проезд по улице.

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице М. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до N и собрали информацию о типе асфальта на каждом из участков — числа t1, t2, . . . , tN (ti — номер типа асфальта на i-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна 3, потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную 1.

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

Формат входных данных
Первая строка входного файла содержит единственное натуральное число N — количество участ- ков дороги (1 <= N <= 100 000). Следующая строка содержит N целых чисел t1, t2, . . . , tN — исходные типы асфальта участков дороги (|ti | <= 109 ). Третья строка содержит единственное натуральное число Q — количество сообщений от жителей об обновлении дорожного покрытия (1 <= Q <= 100 000). Каждая из следующих Q строк содержит очередное сообщение. i-е сообщение представляет собой пару целых чисел pi , ci — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке (1 <= pi <= N, |ci | <= 109 ). Участки дороги нумеруются от 1 до N в порядке задания их исходного типа асфальта во второй строке входного файла.

Формат выходных данных
Выведите Q строк. i-я строка (1 <= i <= Q) должна содержать единственное целое число — величину непроходимости улицы после первых i обновлений дорожного покрытия.

Примеры

Ввод	Вывод
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3	1 3 5 5 3
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9	5 3 4

Замечание
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участ- ков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.
Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.
Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3). Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба (1 ≤ ai ≤ 10⁹ ).

Формат выходного файла
Выходной файл должен содержать одно число — минимальное значение x, для которого Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Пример
Ввод:
10 2
1 2 4 5 2 4 2 2 1 6
Вывод:
7

Пояснение к примеру
В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

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

Входные данные
На вход подается строка, представляющая из себя инфиксную форму записи выражения (в строке отсутствуют пробелы).

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

Примеры

№	Входные данные	Выходные данные
1	(5+3)*(7+2*4)	5 3 + 7 2 4 * + *

Как известно, Саруман Белый - маг очень занятой и каждый день ему приходится работать с огромным количеством древних свитков. Чтобы не запутаться, он дал каждому свитку номер и положил их все на длинную полку. Но последнее время к нему постоянно наведывался Гендальф, чтобы узнать что-нибудь из свитков, что доставляет удовольствие Гендальфу и очень бесит Сарумана. И чтобы не отвечать на огромное количество вопросов Гендальфа где что лежит, он пообещал подарить свой посох тому, кто напишет программу отвечающую на вопросы Гендальфа.
 
Входные данные:
В первой строке задаётся число N(0<=N<=10⁵). На следующих N строках идет описание типа свитка и его номер L (-10⁹<=L<=10⁹). Потом вводится число Q(0<=N<=10⁵) – количество запросов. А затем на еще Q строках вводится тип свитка и его номер (-10⁵<=L<=10⁵).
Типы свитков:
LEG - легендарные
FEW - редкие
STAND – обычные
 
Выходные данные:
На каждый запрос вывести позицию свитка если он есть (Нумерация с 1) и “Fatality error” если такого не имеется. Каждый ответ на новой строке. Так же Гендальфу интересен номер самого большого свитка и самого маленького (Тип свитка на это не влияет). Это необходимо вывести после основных запросов на новой строке по образцу в примере.
 
Пример:
Входные данные:
5
LEG -345
LEG 1
FEW 2452
STAND 4
FEW 334
3
LEG -353
LEG -345
STAND 4
Выходные данные:
Fatality error
1
4
Max 2452 Min -345

Автор: Аксенов Владимир