Алгоритмы сортировки

314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Хаос в библиотеке#82079
В библиотеке произошёл полтергейст! Книги на полке перепутались.  Библиотекарь хочет узнать, насколько сильно книги перепутаны.

Мера хаоса - это количество ИНВЕРСИЙ. Инверсия - это пара книг (i, j), где i < j, но книга i должна стоять ПОСЛЕ книги j (то есть номер книги i больше номера книги j).

Каждая книга имеет уникальный номер от 1 до N. Идеальный порядок: 1, 2, 3, ..., N.

Помогите библиотекарю подсчитать количество инверсий!

ВХОДНЫЕ ДАННЫЕ:
Первая строка: число N (1 ≤ N ≤ 100000) - количество книг.
Вторая строка: перестановка чисел от 1 до N - текущий порядок книг на полке.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество инверсий.
 
Использование сортировкиСортировка слиянием
✓ 2✗ 6—Войти и решать
Шоколадная мудрость#60947

Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.

Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более Bi​ плиток шоколада по цене Аi​ рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада. 

Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец. 


Формат входных данных
В первой строке заданы два числа: N и M (1 <= N, M <= 105). Следующие N строк содержат по 2 числа: Ai (1 <= Ai <= 109) и Bi (1 <= Вi <= 105). \(B_1 + B_2 +... + B_N >= M\).


Формат выходных данных
Выведите минимальную сумму денег, необходимую для покупки M плиток шоколада.
 
Примеры
№ Входные данные Выходные данные
1 2 5
4 9
2 4		 12
2 4 30
6 18
2 5
3 10
7 9		 130
3 1 100000
1000000000 100000		 100000000000000
Алгоритмы сортировкиИспользование сортировки
✓ 16✗ 161800средняяВойти и решать
Сортировка таблицы#55173
В программе Microsoft Excel имеется возможность сортировки таблицы по значениям какого-нибудь столбца. В процессе сортировки переставляются целиком строки таблицы (а не только значения в столбце, по которому осуществляется сортировка). При этом используется устойчивая сортировка, то есть если в этом столбце в нескольких строках стоят одинаковые значения, то эти строки после сортировки будут расположены в том же порядке, что и до сортировки (т.е. раньше будет идти та строка, которая до сортировки шла раньше).

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

Вам требуется написать программу, которая определит, можно ли было как-то оптимизировать последовательность сортировок так, чтобы результат не изменился (независимо от содержания таблицы). Например, если последовательность состоит из двух сортировок по столбцу 1, то можно оставить только одну такую сортировку.

Входные данные
В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 106).  Во второй строке содержатся N натуральных чисел, не превосходящих 105 – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.

Выходные данные
В первую строку  выведите одно число – минимальное количество сортировок, которые требуется произвести. Во второй строке требуется вывести номера столбцов, по которым нужно осуществлять сортировку, в том порядке, в котором следует проводить сортировки.
Быстрая сортировкаСортировка записей
✓ 1✗ 0—Войти и решать
Триангуляция#55069
Вася нарисовал выпуклый N-угольник и провел в нем несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри N-угольника. Теперь он утверждает, что весь N-угольник оказался разбит на треугольники. Напишите программу, которая проверяет истинность Васиного утверждения.

Входные данные
Сначала вводятся числа N - количество вершин N-угольника (3 <= N <= 1000) и M - количество диагоналей, проведенных Васей. Далее на вход программы поступают M пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри N-угольника. Вершины N-угольника нумеруются числами от 1 до N.

Выходные данные
Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число K - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено K чисел - номера вершин исходного N-угольника, которые являются вершинами этой K-угольной части в порядке обхода этой части.
Сканирующая прямаяСортировка подсчетом
✓ 1✗ 0—Войти и решать
Военная сортировка#54665
Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из N чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N, и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число i).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

Входные данные
В первой строке вводится целое число N - размер входного массива (1 <= N <= 100). Вторая строка содержит N целых чисел - исходную перестановку чисел от 1 до N в массиве. Изначально ни одно число не стоит на своем месте.

Выходные данные
Выведите K строк, где K - количество обменов в Вашей сортировке. На каждой строке выведите по два числа xi и yi, разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |xi - yi| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру
В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6
Сортировка "пузырьком"Сортировка выбором (максимума)
✓ 1✗ 2—Войти и решать
Древние цивилизации#54296
Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели N
различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.

Петя предположил, что между цивилизациями A и B
происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.

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

Входные данные
В первой строке вводится число N – количество цивилизаций, культура которых интересует Петю (1≤N≤100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа Si и Ei
 – год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 109
 по абсолютной величине, Si < Ei.

Выходные данные
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.
Быстрая сортировкаСканирующая прямая
✓ 9✗ 106700средняяВойти и решать
Есть n стульев...#49857

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

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

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

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

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


Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

Бинарный поиск по ответуИспользование сортировкиСортировка событий
✓ 31✗ 70300лёгкаяВойти и решать
Наибольший отрезок, не содержащий точек#49417
На числовой прямой отмечено N точек с целочисленными координатами. Определите наибольшую длину отрезка, внутри которого нет ни одной точки. 

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 103). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 109).

Формат выходных данных
В первой строке выведите максимальную длину искомого отрезка. Во второй строке выведите координаты его концов (сначала левую координату, затем через пробел правую). Если таких отрезков несколько, то выведите тот отрезок, у которого наименьшая левая координата.
Использование сортировкиКвадратичные сортировки
✓ 46✗ 85300лёгкаяВойти и решать
Парковка#49011

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

  • появления доступного парковочного места, когда он приезжает;

  • возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i < t^\mathrm{in}_j\) и \(t^\mathrm{out}_i > t^\mathrm{out}_j\).

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

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

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

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

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

Во второй строке набора входных данных через пробел перечислены \(n\) целых чисел \(t^\mathrm{in}_i\) — времена приезда сотрудников на работу (\(1 \le t^\mathrm{in}_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(t^\mathrm{out}_i\) — времена отъезда сотрудников (\(1 \le t^\mathrm{out}_i \le 10^9\)).

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

В первой строке ответа выведите единственное целое число \(k\) — минимальное необходимое количество рядов. В \(i\)-й из следующих \(k\) строк выведите описание \(i\)-го ряда: первое число в строке \(\mathrm{cnt}_i\) должно быть равно количеству мест в ряду, после чего должны следовать \(\mathrm{cnt}_i\) целых чисел от \(1\) до \(n\) — номера сотрудников, занимающих места этого ряда, в порядке от самого глубокого к самому ближнему ко въезду.

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

 
Использование сортировкиСортировка событий
✓ 4✗ 121 100средняяВойти и решать
Скупщик шоколада#39384
Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает купить M плиток шоколада. В городе есть N магазинов, которые продают различный шоколад. В i-м магазине Василий может купить не более Bi плиток шоколада по Ai рублей каждая. Помогите Василию определить, какую минимальную сумму денег ему необходимо накопить, чтобы купить M плиток шоколада?
Гарантируется, что располагая нужной суммой, Василий всегда сможет купить M плиток шоколада.

Входные данные
В первой строке заданы два числа: N и M (1 <= N, M <= 105). Следующие N строк содержат по 2 числа: Ai (1 <= Ai <= 109) и Bi (1 <= Вi <= 105). \(B_1 + B_2 +... + B_N >= M\).

Выходные данные
Выведите минимальную сумму денег, необходимую Василию для покупки M плиток шоколада.
 
Примеры
№ Входные данные Выходные данные
1 2 5
4 9
2 4		 12
2 4 30
6 18
2 5
3 10
7 9		 130
3 1 100000
1000000000 100000		 100000000000000
Алгоритмы сортировкиИспользование сортировки
✓ 47✗ 51800средняяВойти и решать
Новый аэропорт#38992
В аэропорту города Че начал работать новый аэропорт.  В первые сутки работы был записан файл с временем прилета и вылета самолетов. Самолеты, которые улетали на следующие сутки в файл не были записаны. Определите максимальное число самолетов, которые находились в аэропорту одновременно и в течении какого максимального промежутка времени (в минутах) находилось в аэропорту такое число самолетов. Учитываются только самолеты, информация о которых записана в файле.

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

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

Если самолет прилетел в 12:00, а вылетел в 12:01, то считается, что он пробыл в аэропорту 2 минуты.

Файл к заданию
 
Примеры
№ Входные данные Выходные данные
1 6
09:00 10:07
10:20 11:35
12:00 17:00
11:00 11:30
11:20 12:30
11:30 18:15		 4 1
ЕГЭ_информатикаЕГЭ-26. Обработка массива целых чисел. СортировкаСканирующая прямаяСортировка подсчетом
1 500труднаяВойти и решать
Печаль Громозеки#38715
Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.

Входные данные
В первой строке записано целое число N  (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).

Выходные данные
Выведите на экран минимально возможную печаль Громозеки.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 5
2 2 3 5 5		 2 Если мы выберем b = 0, печаль Громозеки будет \(\) 
abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2.
Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2.
2 9
1 2 3 4 5 6 7 8 9		 0  
3 6
6 5 4 3 2 1		 18  
4 7
1 1 1 1 2 3 4		 6  
Алгоритмы сортировкиИспользование сортировкиОдномерные массивы
✓ 2✗ 0—Войти и решать
Автобусы#38571
Новый Президент Тридевятой республики начал свою деятельность с полной ревизии системы общественного транспорта страны. В результате на основе социологических опросов населения было составлено идеальное ежедневное расписание движения междугородних автобусов, утвержденное Парламентом республики.

Более того, было решено заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо более надежными, красивыми и удобными машинами.

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент времени Yi. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени Xi в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления Fi, время отправления Xi, номер города назначения Gi (Fi ≠ Gi), время прибытия Yi, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.
Примеры
№ Входные данные Выходные данные
1 4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30		 8
Жадный алгоритмСканирующая прямаяСортировка подсчетом
✓ 3✗ 19900средняяВойти и решать
Лифт#33123
В современном многоэтажном офисе крупной компании установлен новый лифт. В
компании работает n сотрудников. Для проверки эффективности системы управления
лифтом требуется провести моделирование его работы в конце рабочего дня, когда все
сотрудники должны покинуть здание и спуститься на первый этаж.
В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й
сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной
сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,
либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе
с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый
вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если
несколько вызовов поступает одновременно, активным становится вызов от сотрудника с
меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт
оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже
ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один
этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов
на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него
и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все
люди выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,
активируется вызов, который поступил раньше других. Если несколько вызовов поступило
одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает
обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду
сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия
(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается
решение, на какой вызов лифт должен отреагировать).
Требуется написать программу, которая по описанию вызовов лифта для каждого
сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных
Первая строка входных данных содержит целые числа n и m — количество людей,
вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).
Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых
числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на
котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)
 
Формат выходных данных
Выходные данные должны содержать n целых чисел, для каждого сотрудника
требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
 
Ввод Вывод
5 4
2 3
2 4
5 2
5 3
9 3
 
6
12
6
12
12

 
Пояснение к примеру
Пример работы лифта по шагам показан в следующей таблице. 


Использованные в пояснении к примеру обозначения
Использование сортировкиМножестваСортировка событийСтруктуры данных
✓ 0✗ 91 300средняяВойти и решать
Раскраска отрезков#21847

У Джона Доу есть n отрезков на прямой. Отрезок (a, b) (a < b) — это множество точек x, таких, что a < x < b. Говорят, что отрезки (a1, b1) и (a2, b2) пересекаются, если существует такая точка c, что a1 < c < b1 и a2 < c < b2.

Джон хочет покрасить каждый отрезок в чёрный или белый цвет так, чтобы никакие два отрезка одного цвета не пересекались. Он хочет узнать, сколько существует различных способов покрасить отрезки таким образом.

Две покраски считаются различными, если существует отрезок, который в одной покраске покрашен в белый цвет, а в другой — в чёрный.

Пусть количество способов покрасить отрезки равно x. Выведите остаток от деления x на 106 + 3.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество отрезков у Джона. В следующих n строках находится описание отрезков. В i-й из них записано два числа li и ri (0 ≤ li < ri ≤ 109) — координаты концов i-го отрезка.

Выходные данные

Выведите остаток от деления x (количество способов покрасить отрезки) на 106 + 3.

Примеры тестов

Входные данные

3
1 2
2 3
1 3
Выходные данные
2
Входные данные
3
1 2
1 3
1 4
Выходные данные
0
Входные данные
4
1 2
2 3
3 4
4 5
Выходные данные
16

Примечание

 

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

  • n ≤ 3 — 10 баллов
  • n ≤ 15 — 30 баллов
  • n ≤ 100 — 20 баллов
  • ai ≤ 106 — 20 баллов
  • Без дополнительных ограничений — 20 баллов 
Использование сортировкиСканирующая прямая
✓ 9✗ 371 000средняяВойти и решать
Сортировка времени#18731
Сортировка времени
 
Во входном файле записано сначала число N (1<=N<=100), а затем
N моментов времени. Каждый момент времени задается 3 целыми числами - 
часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60).
 
В выходной файл выведите моменты времени, упорядоченные в порядке
неубывания (момент времени также выводится в виде трех чисел, ведущие нули
выводить не обязательно)
 
Пример входного файла:
4
10 20 30
7 30 00
23 59 59
13 30 30
 
Пример выходного файла:
7 30 0
10 20 30
13 30 30
23 59 59
 
Использование сортировкиСортировка записей
✓ 79✗ 74600лёгкаяВойти и решать
Аркадий Аркадьевич делает грядки#97011

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

Для того чтобы собрать прямоугольную грядку, нужны 4 доски. В идеале это должны быть две пары досок равной длины, тогда из них можно сложить ровный прямоугольник. Но если доски имеют неравную длину, то в одном из углов полученной грядки можно разместить пластиковый уголок: две планки длины \(r\), скреплённые под прямым углом. Уголок со стороной \(r\) позволит увеличить длины двух досок на величину, не превосходящую \(r\). Если противоположными сторонами грядки будут доски длины \(a\) и \(b\), а также \(c\) и \(d\) соответственно, то для того чтобы сделать прямоугольную грядку из этих досок, понадобится уголок размера \(\max(|a-b|, |c-d|)\) . Например, чтобы сделать грядку из досок длины 5, 7, 3, 2, понадобится уголок размера 2. На рисунке чёрным цветом изображены доски и красным цветом изображён уголок.

image

В сарае у Аркадия Аркадьевича нашлись \(n\) досок, \(i\)-я из которых имеет длину \(l_i\). Теперь он хочет выбрать из них четыре и сложить из них грядку таким образом, чтобы использовать уголок наименьшего размера. Помогите ему.

Первая строка входных данных содержит число \(n\) (\(4 \leq n \leq 10^5\)) — количество досок в сарае у Аркадия Аркадьевича.

Следующие \(n\) строк содержат числа \(l_1, \dots, l_n\) (\(1 \leq l_i \leq 10^9\)) — длины досок.

Программа должна сначала вывести число \(r\) — минимально возможный размер уголка.

Во второй строке выведите 4 числа \(a\), \(b\), \(c\), \(d\)  — длины досок, которые необходимо выбрать для грядки. При этом противоположными сторонами прямоугольника будут доски \(a\) и \(b\), а также \(c\) и \(d\). Если есть разные варианты выбора досок для грядки с одной и той же величиной уголка, можно вывести любой из них.

Решения, правильно работающие, когда \(n \leq 30\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(n \leq 100\), будут оцениваться в 45 баллов.

Решения, правильно работающие, когда \(n \leq 500\), будут оцениваться в 65 баллов.

Решения, правильно работающие, когда все \(l_i \leq 30\), будут оцениваться в 10 баллов.

Использование сортировки
✓ 1✗ 8—Войти и решать
Минимум точек, покрывающих все отрезки#94335

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

Точка \(x\) принадлежит отрезку \([l, r]\), если \(l \le x \le r\) (концы включены).

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — минимальное количество точек.

Примечание

В первом примере четыре отрезка: \([1, 6]\), \([2, 8]\), \([7, 12]\), \([10, 16]\). Точки \(x = 6\) и \(x = 10\) вместе попадают в каждый из отрезков: \(6\) — в первые два, \(10\) — в последние два. Меньше двух точек не хватит — отрезки \([1, 6]\) и \([10, 16]\) не пересекаются, одной общей точки у них нет.

Во втором примере все три отрезка содержат точку \(x = 5\), так что одной точки достаточно.

Сканирующая прямая
—Войти и решать
Сумма попарных пересечений#94334

На числовой прямой даны \(n\) отрезков. Для каждой неупорядоченной пары отрезков \((i, j)\) рассмотрим длину их пересечения. Если отрезки не пересекаются — длина пересечения равна нулю.

Найдите сумму длин пересечений по всем парам.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — сумма длин пересечений по всем неупорядоченным парам отрезков. Ответ может не помещаться в 32-битный тип.

Примечание

В первом примере три отрезка: \([0, 10]\), \([2, 6]\), \([8, 15]\).

  • Пересечение первого и второго — \([2, 6]\) длины \(4\).
  • Пересечение первого и третьего — \([8, 10]\) длины \(2\).
  • Пересечение второго и третьего пусто.

Сумма: \(4 + 2 + 0 = 6\).

Во втором примере четыре одинаковых отрезка длины \(10\). Каждая из \(\binom{4}{2} = 6\) пар даёт пересечение длины \(10\), итого \(60\).

Сканирующая прямая
—Войти и решать
Самый глубокий отрезок#94333

На числовой прямой даны \(n\) отрезков. Назовём глубиной отрезка \(i\) количество отрезков \(j\) (включая сам отрезок \(i\)), которые целиком его содержат: \(l_j \le l_i\) и \(r_i \le r_j\).

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

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

В первой строке — целое число \(n\) (\(1 \le n \le 5000\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — максимальная глубина.

Примечание

В первом примере отрезок \([3, 4]\) содержится в \([2, 5]\), который, в свою очередь, содержится в \([1, 10]\). Глубина \([3, 4]\) равна \(3\): его содержат он сам, \([2, 5]\) и \([1, 10]\). Это максимум.

Во втором примере все три отрезка совпадают, и каждый «содержится» в каждом — глубина равна \(3\).

Сканирующая прямая
—Войти и решать
Поделиться
Класснуть