На числовой прямой окрасили \(N\) отрезков. Известны координаты левого и правого концов каждого отрезка (\(L_i\) и \(R_i\)). Найти длину окрашенной части числовой прямой.
В первой строке находится число \(N\), в следующих \(N\) строках - пары \(L_i\) и \(R_i\). \(L_i\) и \(R_i\) - целые, \(-10^9 \leq L_i \leq R_i \leq 10^9, \, 1 \leq N \leq 15000\)
Вывести одно число - длину окрашенной части прямой.
| Ввод | Вывод |
|---|---|
1 10 20 |
10 |
1 10 10 |
0 |
Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.
В первой строке содержится натуральное число \(N \leq 10^5\) – количество друзей Тома Сойера. Далее идет \(N\) пар целых неотрицательных чисел – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок – целые числа от 1 до \(10^9\).
Программа должна вывести единственное число – суммарное количество покрашенных досок.
| Ввод | Вывод |
|---|---|
3 1 2 3 4 2 3 |
4 |
Дано \(n\) отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка \(x\) считается принадлежащей отрезку с концами \(a\) и \(b\) , если выполняется двойное неравенство \(\min(a, b) \leq x \leq \max(a, b)\).
Первая строка содержит два целых числа \(n \ (1 \leq n \leq 10^5)\) – число отрезков и \(m \ (1 \leq m \leq 10^5 )\) – число точек. В следующих \(n\) строках по два целых числи \(a_i\) и \(b_i\) – координаты концов соответствующего отрезка(например, может быть пара 5 2). В последней строке \(m\) целых чисел – координаты точек. Все числа по модулю не превосходят \(10^9\).
В выходной файл выведите \(m\) чисел – для каждой точки количество отрезков, в которых она содержится.
| Ввод | Вывод |
|---|---|
3 2 0 5 -3 2 7 10 1 6 |
2 0 |
1 3 -10 10 -100 100 0 |
0 0 1 |
На одном из московских вокзалов билеты продают \(N\) касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
Сначала вводится одно целое число \(N\) \((0 \leq N \leq 10000)\).
В каждой из следующих \(N\) строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все \(N\) касс.
| Ввод | Вывод |
|---|---|
3 1 0 0 23 0 0 12 0 0 12 0 0 22 0 0 2 0 0 |
7200 |
2 9 30 0 14 0 0 14 15 0 21 0 0 |
0 |
2 14 0 0 18 0 0 10 0 0 14 0 1 |
1 |
На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (\(M\) — натуральное число), содержащее наименьшее число отрезков.
В первой строке указана константа \(M\) (\(1 \leq M \leq 5000\)). В каждой последующей строке записана пара чисел \(L_i\) и \(R_i\) (\(|L_i|, |R_i| \leq 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает \(10^5\).
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0, M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0, M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.
| Ввод | Вывод |
|---|---|
1 -1 0 -5 -3 2 5 0 0 |
No solution |
1 -1 0 0 1 0 0 |
1 0 1 |
На конференции работников народного образования с докладами об очередном улучшении финансирования школ желает выступить \(N\) министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.
Первая строка входных данных содержит натуральное число \(N \leq 10^4\). Далее идет \(N\) строк, каждая из которых содержит два целых числа \(S_i\) и \(T_i\), \(0 \leq S_i \leq T_i \leq 10^9\). Каждая строка соответствует одной заявке с номером \(i\) \((1 \leq i \leq N)\), \(S_i\) является временем начала заявки, \(T_i\) – временем ее окончания.
Программа должна найти подмножество множества \(\{1, 2, \ldots, n\}\), содержащее наибольшее число элементов, такое, что для любых двух элементов \(i\) и \(j\) из найденного подмножества верно одно из двух неравенств: \(T_i \leq S_j\) или \(T_j \leq S_i\). Указанные неравенства означают, что заявки с номерами \(i\) и \(j\) не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра)
Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.
| Ввод | Вывод |
|---|---|
5 12 17 45 49 23 45 49 50 60 70 |
5 |
5 15 25 20 30 10 20 30 40 25 35 |
3 |