Страница: 1 Отображать по:
#2531
Москва — Ханты-Мансийск
  
ограничение по времени на тест
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
    #2534
    Земледелие 2.0
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.

    Для получения большего урожая Архип решил удобрить некоторый прямоугольный фрагмент поля, состоящий из целых участков. В выбранном фрагменте Архип удобряет каждый участок. Повторное удобрение участка делает его непригодным к выращиванию брюссельской редиски. Закончив удобрять, фермер выбирает для посадки редиски прямоугольный фрагмент поля, состоящий из целых участков, каждый из которых удобрен ровно один раз.

    Архип должен выбрать на поле фрагмент для удобрения таким образом, чтобы фрагмент для посадки редиски имел максимальную площадь.

    Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.

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

    В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.

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

    Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).

    Вторая строка должна описывать фрагмент под посадку в том же формате.

    Третья строка должна содержать площадь фрагмента (количество участков) под посадку.

    Если решений несколько, выведите любое.

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

    Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.

    Примеры
    Входные данные
    4 4
1110
1010
1110
0000
    Выходные данные
    2 2 2 2
1 1 3 3
9
    Страница: 1 Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест