Темы --> Информатика --> Алгоритмы --> Жадный алгоритм
---> 70 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Есть $n$ человек, которые хотят улететь из Москвы в Ханты-Мансийск. Каждый день летает один самолёт вместимостью $k$ человек. У каждого человека есть множество дней, когда он может улететь, — отрезок $[a_i,b_i]$. Нужно придумать такое распределение людей по самолётам, что до Ханты-Мансийска долетит максимальное число людей. Среди людей есть участники РОИ, которых нужно перевезти обязательно (остальных людей будем называть обычными).

В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за $m$ дней, пронумерованных от 1 до $m$, из Москвы в Ханты-Мансийск хотят вылететь $n$ пассажиров, в том числе и участники олимпиады.

Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета $i$-го пассажира указана в виде пары чисел $(a_i, b_i)$. Это означает, что пассажир согласен вылететь в любой день, начиная с $a_i$ и по $b_i$ включительно, и не может вылететь в другие дни.

Самолёт из Москвы в Ханты-Мансийск вылетает всего один раз в день и вмещает не более $k$ пассажиров. Необходимо распределить пассажиров по дням вылета таким образом, чтобы улетело как можно большее количество пассажиров, при этом все участники Всероссийской олимпиады должны улететь обязательно.

Напишите программу, определяющую распределение пассажиров по дням вылета, при котором максимизируется количество перевезённых пассажиров, или определяющую, что такого распределения не существует.

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

В первой строке входного файла записаны три натуральных числа — $n$, $m$ и $k$ ($1\le n\le100\,000$, $1\le m\le100\,000$, $1\le k\le100\,000$). Далее следуют $n$ строк, $i$-я из которых содержит результаты заполнения анкеты пассажиром с порядковым номером $i$ в виде трёх целых чисел, первые два из которых — самый ранний и самый поздний дни вылета $a_i$ и $b_i$ ($1\le a_i\le b_i\le m$), а последнее число равно 0, если пассажир не является участником Всероссийской олимпиады, и равно 1, если является. Гарантируется, что хотя бы один пассажир является участником Всероссийской олимпиады. Числа в каждой строке разделены пробелами.

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

В первой строке выходного файла выведите максимальное количество пассажиров $l$, которых можно перевезти из Москвы в Ханты-Мансийск. Если невозможно выполнить поставленную задачу, то в первой строке необходимо вывести число 0. В случае положительного ответа выведите во второй строке n чисел, а именно, для каждого пассажира выведите номер дня, в который запланирован его вылет, либо 0, если этому пассажиру не нашлось места в оптимальном распределении. Числа во второй строке разделяйте пробелами. Если оптимальных распределений несколько, выведите любое из них.

Система оценивания

  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 10, будут оцениваться из 20 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 100, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 1 000, будут оцениваться из 60 баллов.
  • Решения, корректно работающие при $n$, $m$ и $k$, не превышающих 10 000, будут оцениваться из 80 баллов.

  • Примеры
    Входные данные
    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 
    
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    64 megabytes

    В этой задаче Вася готовится к олимпиаде. Учитель дал ему 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
    ограничение по времени на тест
    1.0 second;
    ограничение по памяти на тест
    64 megabytes

    В этой задаче Вася готовится к олимпиаде. Учитель дал ему 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
    
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Директор школы «Лицей Программистов» города Линейска сумел привить ученикам этой школы хорошую дисциплину, но, несмотря на это, многие ученики продолжают опаздывать на уроки.

    В Линейске есть всего одна главная улица, на которой расположен и сам лицей, и живут все его ученики. Дисциплинированные школьники выходят из своих домов в одно и то же время. Но, к сожалению, все они живут на разном расстоянии от школы и добираются с разной, но постоянной скоростью (среди учеников есть как весьма неторопливые, так и будущая чемпионка мира по бегу на 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

    Страница: << 3 4 5 6 7 8 9 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест