Информатика

На числовой прямой даны \(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\).

На числовой прямой даны \(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\).

На числовой прямой даны \(n\) отрезков. Требуется разбить их на минимальное число групп так, чтобы внутри каждой группы любые два отрезка не пересекались. При этом стыковка концом-к-началу пересечением не считается: отрезки \([a, b]\) и \([b, c]\) могут попасть в одну группу.

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

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

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

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

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

Одно целое число — минимум групп.

Примечание

В первом примере отрезки \([0, 30]\), \([5, 10]\), \([15, 20]\), \([25, 35]\). В одну группу можно положить \([5, 10]\), \([15, 20]\) и \([25, 35]\) — они попарно не пересекаются. Отрезок \([0, 30]\) пересекается с каждым из них и требует отдельной группы. Итого: \(2\).

Во втором примере отрезки \([10, 20]\) и \([20, 30]\) стыкуются по точке \(20\), и по условию это не считается пересечением. Поэтому одной группы достаточно.

На числовой прямой задан целевой отрезок \([L, R]\) и \(n\) отрезков-«покрывал». Определите, покрывают ли эти \(n\) отрезков целевой отрезок целиком — то есть каждая точка из \([L, R]\) принадлежит хотя бы одному из них.

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

В первой строке — два целых числа \(L\) и \(R\) (\(-10^9 \le L \le R \le 10^9\)) — концы целевого отрезка.

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

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

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

Выведите YES, если каждая точка целевого отрезка \([L, R]\) покрыта хотя бы одним из данных отрезков, и NO иначе.

Примечание

В первом примере отрезки \([0, 4]\), \([3, 7]\), \([6, 10]\) вместе покрывают всю цель \([0, 10]\) без пропусков.

Во втором примере между точками \(4\) и \(6\) есть пропуск (точка \(5\) не покрыта ни одним отрезком), поэтому ответ NO.

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

Найдите суммарную длину закрашенной части прямой.

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

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

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

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

Одно целое число — длина объединения всех данных отрезков.

Примечание

В первом примере отрезки \([1, 5]\) и \([3, 7]\) сливаются в один отрезок \([1, 7]\) длины \(6\). Отдельный отрезок \([10, 12]\) добавляет ещё \(2\). Итого: \(8\).

Во втором примере четыре отрезка стыкуются концом-к-началу и образуют один сплошной отрезок \([0, 4]\) длины \(4\).

На числовой прямой нарисованы \(n\) отрезков. Концы отрезков заданы целыми числами. Точка \(x\) считается принадлежащей отрезку \([s, f]\), если \(s \le x \le f\) (концы включены).

Найдите такую целую точку \(x\), которой одновременно принадлежит максимальное количество данных отрезков. Если таких точек несколько, выведите наименьшую из них.

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

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

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

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

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

Примечание

В первом примере отрезки \([0,1]\), \([0,2]\), \([1,2]\). Точка \(x = 1\) принадлежит всем трём отрезкам, и это наименьшая такая точка.

Во втором примере точка \(x = 1\) принадлежит двум отрезкам: \([0,1]\) и \([1,3]\). Это максимум, достигаемый раньше всего на прямой.

Ночью на сибирской трассе одновременно сошло \(n\) снежных заносов. Каждый занос перекрывает участок дороги между километровыми отметками \(a_i\) и \(b_i\) включительно. Сообщения о заносах поступали диспетчеру по рации в произвольном порядке, поэтому \(a_i\) может оказаться как меньше, так и больше \(b_i\): занос покрывает все километровые отметки от \(\min(a_i, b_i)\) до \(\max(a_i, b_i)\) включительно.

К утру с трассы поступили \(m\) запросов от водителей. Каждый водитель называет километровую отметку \(p_j\), на которой он сейчас находится, и просит сообщить, сколько заносов перекрывают этот километр. Помогите диспетчеру быстро ответить на все запросы.

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

В первой строке записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 50\,000\)) — количество заносов и количество запросов.

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

В последней строке через пробел записаны \(m\) целых чисел \(p_1, p_2, \ldots, p_m\) (\(-10^9 \le p_j \le 10^9\)) — километровые отметки, о которых спрашивают водители.

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

Выведите \(m\) целых чисел через пробел: для каждой отметки \(p_j\) — количество заносов, перекрывающих этот километр.

Примечание

Точка считается принадлежащей участку с концами \(a\) и \(b\), если выполняется неравенство \(\min(a, b) \le p \le \max(a, b)\). Совпадение с границей засчитывается.

На странице есть:

<ul id="list"></ul>

JavaScript выполняет:

const ul = document.getElementById('list');
ul.innerHTML = '';
const li = document.createElement('li');
li.textContent = 'Бег';
ul.appendChild(li);

Что увидит пользователь?

1. Пустой список
2. Список с одним пунктом «Бег»
3. Ошибку в консоли
4. Текст «Бег» без маркера списка

Что произойдёт при выполнении этого кода?

fetch('/api/add', {
  method: 'POST',
  headers: {'Content-Type': 'application/json'},
  body: JSON.stringify({name: 'Бег'})
})
.then(r => r.json())
.then(data => alert(data.msg));

1. Откроется новая страница /api/add
2. Страница перезагрузится с новой привычкой
3. JavaScript отправит POST с JSON на сервер, получит ответ и покажет alert
4. Привычка добавится, но ничего не произойдёт на экране

Чем отличается return jsonify({"count": 5}) от return '{"count": 5}'?

1. Ничем — оба возвращают одинаковый текст
2. jsonify шифрует данные, а строка — нет
3. jsonify добавляет правильный заголовок Content-Type: application/json
4. jsonify работает быстрее строки

Пользователь нажал кнопку «Добавить» в HTML-форме:

<form method="POST" action="/add">
  <input name="habit_name" value="Йога">
  <button type="submit">Добавить</button>
</form>

Как Flask получит значение «Йога» в обработчике?

1. request.json['habit_name']
2. request.form['habit_name']
3. request.args['habit_name']
4. request.get('habit_name')

Ты ввёл silvertests.ru в адресной строке и нажал Enter. В каком порядке всё происходит?

1. HTTP-запрос → DNS → HTTP-ответ → отрисовка
2. Отрисовка → HTTP-ответ → DNS → HTTP-запрос
3. DNS → HTTP-ответ → HTTP-запрос → отрисовка
4. DNS → HTTP-запрос → HTTP-ответ → отрисовка

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

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

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

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

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

Во второй строке — \(n\) целых чисел \(p_i\) (\(0 \le p_i \le 10^9\)), разделённых пробелами, — рейтинг каждого ученика.

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

Одно целое число — максимальный суммарный рейтинг команды.

Примечание

В первом примере нужно выбрать трёх учеников из пяти. Лучше всего взять с рейтингами 8, 5 и 3 — в сумме 16.

Во втором примере в команду идут все четверо учеников, поэтому ответ — сумма всех рейтингов.

Библиотекарь расставляет книги на полке длиной \(W\) сантиметров. У него есть \(n\) книг; \(i\)-я книга имеет размеры \(a_i \times b_i\) сантиметров.

Каждую книгу можно поставить на полку двумя способами: одной стороной к соседней книге (тогда она занимает вдоль полки \(a_i\) сантиметров) или другой стороной (тогда \(b_i\) сантиметров). Способ расстановки выбирается для каждой книги независимо.

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

Помогите ему определить это максимальное число книг.

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le W \le 10^{14}\)) — количество книг и длина полки.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры \(i\)-й книги.

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

Одно целое число — максимальное количество книг, которые можно расставить на полке.

На стройплощадку нужно перевезти доски. У бригадира есть грузовик с длинным узким кузовом длиной \(L\) сантиметров — доски укладываются в кузов в один ряд вдоль кузова. На складе лежат \(n\) досок; каждая доска имеет две стороны: толщину \(a_i\) и ширину \(b_i\) сантиметров.

Каждую доску можно положить в кузов двумя способами: плашмя (тогда она занимает вдоль кузова \(a_i\) сантиметров) или на ребро (тогда \(b_i\) сантиметров). Способ укладки выбирается для каждой доски независимо.

Бригадир хочет за один рейс увезти максимальное количество досок. Какие именно — неважно: нужно лишь максимизировать число досок в кузове. Суммарная длина уложенных досок не должна превышать длины кузова.

Определите это максимальное число.

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

В первой строке — два целых числа \(n\) и \(L\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le L \le 10^{14}\)) — количество досок на складе и длина кузова в сантиметрах.

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

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

Одно целое число — максимальное количество досок, которые можно увезти за один рейс.

Примечание

В первом примере выгодно каждую доску укладывать той стороной, которая короче. Тогда доски займут 2, 4, 3 и 1 см — всего 10 см, помещаются все 4.

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

Школьник Тимур участвует в серии онлайн-соревнований по программированию. За весь год проходит \(n\) соревнований, и Тимур заранее знает, сколько очков он может набрать в каждом из них: за \(i\)-е соревнование он получит \(s_i\) очков.

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

Помогите ему вычислить эту максимальную сумму.

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

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 10^5\)) — общее количество соревнований и сколько из них идут в зачёт.

Во второй строке — \(n\) целых чисел \(s_i\) (\(0 \le s_i \le 10^9\)), разделённых пробелами, — количество очков за каждое соревнование.

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

Одно целое число — максимальная суммарная сумма очков за \(k\) выбранных соревнований.

Примечание

В первом примере из пяти соревнований с очками \(1, 5, 3, 8, 2\) надо выбрать три. Лучше всего взять соревнования с очками 8, 5 и 3 — в сумме 16.

Во втором примере в зачёт идут все соревнования, так что ответ — сумма всех очков.

Вдоль прямой трассы расположено \(n\) посёлков. У каждого посёлка известна его координата на трассе — целое число \(p_i\). Связисты хотят покрыть все посёлки радиосигналом, установив на трассе несколько радиовышек.

Каждая вышка имеет радиус покрытия 1 километр: она покрывает всё, что находится на расстоянии не более 1 от её координаты. То есть вышка, установленная в точке \(x\), покрывает отрезок \([x - 1; \, x + 1]\). Посёлок считается покрытым, если его координата попадает в покрытие хотя бы одной вышки (граничная точка тоже считается покрытой).

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

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

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

Во второй строке — \(n\) целых чисел \(p_i\) (\(-10^9 \le p_i \le 10^9\)), разделённых пробелами, — координаты посёлков. Координаты могут повторяться (несколько посёлков в одной точке).

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

Одно целое число — минимальное количество радиовышек, необходимое для покрытия всех посёлков.

Примечание

В первом примере посёлки находятся в точках 1, 3, 5. Одна вышка, установленная в точке 2, покроет отрезок \([1; 3]\) и захватит посёлки в точках 1 и 3. Для посёлка в точке 5 нужна ещё одна вышка, например в точке 4 или в точке 5. Итого 2 вышки.

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

Центр управления отправляет на Марс грузовую капсулу. Она может поднять не более \(W\) килограммов полезной нагрузки. Учёные отобрали \(n\) научных приборов, которые хотят отправить в этой миссии; масса каждого прибора равна \(w_i\) килограммов.

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

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

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 10^5\), \(1 \le W \le 10^9\)) — количество приборов и грузоподъёмность капсулы в килограммах.

Во второй строке — \(n\) целых чисел \(w_i\) (\(1 \le w_i \le 10^4\)), разделённых пробелами, — масса каждого прибора в килограммах.

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

Одно целое число — максимальное количество приборов, которые можно отправить на Марс.

Примечание

В первом примере лучше всего отправить приборы массами \(1 + 2 + 3 + 4 = 10\) кг — ровно помещаются в капсулу, итого 4 прибора. Прибор массой 7 кг остаётся на Земле.

Во втором примере каждый прибор по отдельности весит больше грузоподъёмности капсулы. Ни один прибор отправить нельзя.

В актовом зале школы может проходить только одно мероприятие в каждый момент времени. На проведение актового зала подано \(n\) заявок от разных кружков. Каждая заявка — это интервал времени \([l_i; r_i]\): кружок хочет занять зал с минуты \(l_i\) по минуту \(r_i\) включительно.

Два кружка не могут проходить в зале одновременно: если один занимает время \([l_1; r_1]\), а другой — \([l_2; r_2]\), эти интервалы не должны пересекаться. Если один кружок заканчивается ровно в ту минуту, когда начинается другой, это тоже считается пересечением.

Директор хочет одобрить как можно больше заявок. Какое максимальное количество кружков можно разместить в зале за день?

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

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

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

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

Одно целое число — максимальное количество заявок, которые можно одобрить.

Примечание

В первом примере можно одобрить заявки \([1; 3]\) и \([4; 7]\) — они не пересекаются.

Во втором примере оптимально взять \([2; 3]\) и \([5; 7]\).

На столе лежит n верёвок разной длины. Вам нужно связать их все в одну длинную верёвку. За одну операцию можно взять любые две верёвки и связать их в одну — стоимость такой операции равна сумме длин этих двух верёвок.

Например, если связать верёвки длиной 3 и 5, получится одна верёвка длиной 8, а стоимость операции — 8. Эту новую верёвку можно затем связывать с другими.

Требуется найти минимальную суммарную стоимость, за которую можно связать все n верёвок в одну.
 

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

В первой строке записано натуральное число n (1 ≤ n ≤ 50 000) — количество верёвок.

Во второй строке через пробел записаны n натуральных чисел a₁, a₂, …, a_n (1 ≤ a_i ≤ 10 000) — длины верёвок.
 

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

Выведите одно целое число — минимальную суммарную стоимость связывания всех верёвок в одну. Если верёвка одна (n = 1), выведите 0.

Внимание: ответ может не помещаться в 32-битный целочисленный тип. В языке C++ используйте тип long long; в Python ограничений нет.
 

Пояснение к первому примеру

Оптимальная последовательность: связываем 2 и 3 (стоимость 5), получаем набор {4, 5, 6}. Связываем 4 и 5 (стоимость 9), получаем {6, 9}. Связываем 6 и 9 (стоимость 15). Итого: 5 + 9 + 15 = 29.