Информатика

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

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

Дана последовательность вещественных чисел \(a_1, a_2, \dots, a_N\) и целое число \(K\). Для каждого индекса \(i\), удовлетворяющего условию \(K+1 \le i \le N-K\), рассмотрим множество его \(2K\) соседей: \[S_i = \{ a_{i-K}, \dots, a_{i-1}, a_{i+1}, \dots, a_{i+K} \}.\] Вычислим среднее арифметическое элементов этого множества: \[\mu_i = \frac{1}{2K} \sum_{x \in S_i} x\] и их стандартное отклонение: \[\sigma_i = \sqrt{ \frac{1}{2K} \sum_{x \in S_i} (x - \mu_i)^2 }.\] Элемент \(a_i\) называется выбросом, если выполняется неравенство \[|a_i - \mu_i| > 2\sigma_i.\] Если \(\sigma_i = 0\) (все числа в \(S_i\) равны), то условие превращается в \(|a_i - \mu_i| > 0\), то есть \(a_i\) считается выбросом, когда он отличается от этого общего значения.

Требуется определить количество выбросов среди всех элементов, для которых определена окрестность (т. е. для \(i = K+1, K+2, \dots, N-K\)).

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

Входные данные
Первая строка содержит два целых числа \(N\) и \(K\) (\(1 \le K \le \lfloor N/2 \rfloor\), \(N \le 200\,000\)). Вторая строка содержит \(N\) вещественных чисел \(a_1, a_2, \dots, a_N\), разделенных пробелами

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

Выведите одно целое число — количество выбросов.
 

Примеры

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

<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\)-й книги.

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

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