--->
71 задач
<---
Источники
Есть \(n\) человек, которые хотят улететь из Москвы в Ханты-Мансийск. Каждый день летает один самолёт вместимостью \(k\) человек. У каждого человека есть множество дней, когда он может улететь, — отрезок \([a_i,b_i]\). Нужно придумать такое распределение людей по самолётам, что до Ханты-Мансийска долетит максимальное число людей. Среди людей есть участники РОИ, которых нужно перевезти обязательно (остальных людей будем называть обычными).
В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за \(m\) дней, пронумерованных от 1 до \(m\), из Москвы в Ханты-Мансийск хотят вылететь \(n\) пассажиров, в том числе и участники олимпиады.
Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета
Самолёт из Москвы в Ханты-Мансийск вылетает всего один раз в день и вмещает не более \(k\) пассажиров. Необходимо распределить пассажиров по дням вылета таким образом, чтобы улетело как можно большее количество пассажиров, при этом все участники Всероссийской олимпиады должны улететь обязательно.
Напишите программу, определяющую распределение пассажиров по дням вылета, при котором максимизируется количество перевезённых пассажиров, или определяющую, что такого распределения не существует.
В первой строке входного файла записаны три натуральных числа — \(n\), \(m\) и \(k\) (\(1\le n\le100\,000\), \(1\le m\le100\,000\), \(1\le k\le100\,000\)). Далее следуют \(n\) строк,
В первой строке выходного файла выведите максимальное количество пассажиров \(l\), которых можно перевезти из Москвы в Ханты-Мансийск. Если невозможно выполнить поставленную задачу, то в первой строке необходимо вывести число 0. В случае положительного ответа выведите во второй строке n чисел, а именно, для каждого пассажира выведите номер дня, в который запланирован его вылет, либо 0, если этому пассажиру не нашлось места в оптимальном распределении. Числа во второй строке разделяйте пробелами. Если оптимальных распределений несколько, выведите любое из них.
Система оценивания
3 2 1 1 2 1 1 2 0 1 2 1
2 1 0 2
3 4 1 1 2 1 1 3 1 1 4 0
3 1 2 3
10 4 2 2 3 0 2 3 0 1 3 1 3 4 0 3 4 1 2 3 0 2 2 0 1 3 1 4 4 0 2 4 0
8 2 3 1 4 4 3 2 1 0 0
В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100 000) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.
Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100 000, 0 ≤ A ≤ 109) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 109, 1 ≤ bi ≤ 109) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Выведите одно число — максимальное количество задач, которое Вася сможет решить.
3 2 3 1 2 1 1 1
3
В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.
Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100, 0 ≤ A ≤ 100) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 100, 1 ≤ bi ≤ 100) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Выведите одно число — максимальное количество задач, которое Вася может решить.
В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3. Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.
3 2 3 1 2 1 1 1
3
4 1 1 10 21 5 1 10 100 100
3
На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все \(n\) своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке \(a_1\), \(a_2\), ..., \(a_n\). Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами \(i_1\), \(i_2\), ...., \(i_k\) покрашены в один цвет, то \(a_{i_1} \lt a_{i_2}\lt ... \lt a_{i_k}\). Петя хочет использовать как можно меньше цветов. Помогите ему!
Первая строка входного файла содержит число \(n\) - количество кубиков у Пети (\(1\le n \le 250000\)). В следующей строке записано \(n\) чисел \(a_1\), \(a_2\), ..., \(a_k\), \(-2^{31}\le a_i \le 2^{31} - 1\).
На первой строке выходного файла выведите число \(m\) — наименьшее количество цветов, которое потребуется Пете. На следующей строке выведите \(n\) чисел из диапазона от 1 до \(m\) — цвета, в которые Петя должен покрасить кубики.
10 2 3 1 3 2 1 2 2 4 3
5 1 1 2 2 3 4 4 5 1 3
Директор школы «Лицей Программистов» города Линейска сумел привить ученикам этой школы хорошую дисциплину, но, несмотря на это, многие ученики продолжают опаздывать на уроки.
В Линейске есть всего одна главная улица, на которой расположен и сам лицей, и живут все его ученики. Дисциплинированные школьники выходят из своих домов в одно и то же время. Но, к сожалению, все они живут на разном расстоянии от школы и добираются с разной, но постоянной скоростью (среди учеников есть как весьма неторопливые, так и будущая чемпионка мира по бегу на 100 метров Маша Гайка).
Для улучшения ситуации с опозданиями школа купила один веломобиль, который взялся водить сторож школы. Веломобиль способен помимо водителя перевозить одного школьника. Веломобиль перемещается с постоянной скоростью \(v\).
Ночь веломобиль проводит в школьном гараже, а утром, ровно в тот момент, когда все ученики выходят из своих домов, отправляется им навстречу, чтобы подвезти какого-нибудь школьника. Конечно же, ему приходится подвозить школьника прямо до ворот школы, потому как никто не хочет быть высаженным посреди пути. После того, как веломобиль помог одному ученику быстрее добраться в учебное заведение, он снова может ехать навстречу следующему опаздывающему человеку.
Директор хочет начинать занятия как можно раньше, но для этого нужно, чтобы все ученики добрались до лицея. Он поручил вам помочь составить план, по которому должен действовать водитель веломобиля, чтобы время прибытия последнего школьника в школу было минимальным.
Первая строка входного файла содержит два целых числа \(n, v\) (\(1 \le n \le 10^5\), \(1 \le v \le 1000\)) — соответственно количество людей и скорость веломобиля. Следующие \(n\) строк содержат по два целых числа \(x_i, v_i\) (\(1 \le x_i, v_i \le 1000\)) — расстояния от школы до дома \(i\)-ого ученика и его скорость.
В первую строку выходного файла выведите вещественное число \(t\) — минимальное время, за которое все школьники доберутся до лицея. Во второй строке выходного файла выведите единственное число \(k\) — количество учеников, которых нужно подвезти. В следующих \(k\) строках выведите по два числа — номер школьника, которого нужно подвезти, и расстояние от школы, на котором этот школьник должен сесть в веломобиль.
Школьников нужно выводить в том же порядке, в котором они будут ехать на веломобиле.
Выводите все вещественные числа как можно точнее. При проверке вашего решения при сравнении вещественных чисел будет допускаться абсолютная или относительная погрешность \(10^{-6}\).
Пример5 4 1 1 4 2 3 1 7 5 5 1 | 2.400000000 2 5 4.000000000 3 0.800000000 |