Пересечение множеств


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38308. Реклама
Темы: Пересечение множеств   

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня.

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

Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик целиком от начала до конца хотя бы один раз. Ролик длится ровно 5 единиц времен. Трансляции роликов не должны пересекаться, то есть начало второй трансляции должно быть хотя бы на 5 единиц времени позже, чем начало первой.

Если трансляция ролика включается, например, в момент времени 10, то покупатели, пришедшие в супермаркет в момент времени 10 (или раньше) и уходящие из супермаркета в момент 15 (или позднее) успеют его прослушать целиком, а, например, покупатель, пришедший в момент времени 11, равно как и покупатель, уходящий в момент 14 - не успеют. Если покупатель успевает услышать только конец первой трансляции ролика (не сначала) и начало второй трансляции (не до конца), то считается, что он не услышал объявления. Если покупатель успевает услышать обе трансляции ролика, то при подсчете числа людей, прослушавших ролик, он все равно учитывается всего один раз (фирме важно именно количество различных людей, услышавших ролик).

Входные данные
В первой строке входного файла вводится  число N - количество покупателей (1<=N<=2000). В следующих N строках записано по паре натуральных чисел - время прихода и время ухода каждого из них. Все значения времени - натуральные числа, не превышающие 109. Время ухода человека из супермаркета всегда строго больше времени его прихода в супермаркет.

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

Примеры
№ Входные данные Выходные данные Пояснение
1 4
1 11
1 3
6 15
1 6		 3 1 6 Трансляция роликов начинается в моменты времени 1 и 6. Первое объявление успевают прослушать покупатели номер 1 и 4, второе - 1 и 3. Когда бы ни начиналась трансляция объявления, 2-й покупатель не сможет его прослушать, так как находится в супермаркете менее 5 минут. Приведенный ответ является не единственным верным ответом на этот тест.
2 1
1 10		 1 3 25 Объявление, трансляция которого начинается в момент 3, единственный покупатель обязательно услышит. Вторую трансляцию (раз она оплачена) мы можем сделать когда угодно, например, в 25 минут в пустом супермаркете (впрочем, мы не можем начать трансляцию второго объявления, например, в момент 7 - т.к. к этому моменту еще не закончится первая трансляция)
3 3
1 10
11 20
21 30		 2 1 22 Объявление услышат лишь 2 из 3-х покупателей.

ID 38310. Пересадки
Темы: Пересечение множеств    Отрезки   

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

Входные данные
Вводятся четыре числа, не превосходящие 100, задающие номера конечных остановок. Сначала для первого, потом второго автобуса (см. примеры и рисунок).

Выходные данные
Ваша программа должна выводить одно число – искомое количество остановок.

Примеры
№ Входные данные Выходные данные Пояснение
1 3 6 4 2 2 первый автобус ходит с 3-й остановки по 6-ю и обратно, а второй с 2-й по 4-ю и обратно. Пересесть с одного автобуса на другой можно на 3-й и 4-й остановках. Их две.
2 3 1 5 10 0 автобусы не имеют общих остановок.

ID 38991. Реклама 2
Темы: Пересечение множеств    Быстрая сортировка   

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

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

Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.

Входные данные
Во входных данных записано сначала число N — количество покупателей, посетивших супермаркет за день(1<N<3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<Ai<Bi<106).

Выходные данные
Выведите сначала количество рекламных объявлений, которое будет протранслировано за день. Затем выведите в возрастающем порядке моменты времени, в которые нужно транслировать рекламные объявления.

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

Примеры
№ Входные данные Выходные данные
1 5
1 10
10 12
1 10
1 10
23 24		 5
5 10 12 23 24

ID 43772. Треугольник Максима
Темы: "Два указателя"    Пересечение множеств   

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

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

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

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

Входные данные
Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера (2 ≤ n ≤ 1000). Последующие n строк содержат записи Максима, причём каждая строка содержит две компоненты: вещественное число fi — частоту, выставленную на тюнере, в герцах (30 ≤ fi ≤ 4000), и слово «closer» или слово «further» для каждой частоты, кроме первой.

Слово «closer» означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |fi−fтреуг.| < |fi−1−fтреуг.|

Слово «further» означает, что частота данной ноты дальше, чем предыдущая.

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

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

Выходные данные
В выходной файл необходимо вывести через пробел два вещественных числа — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом. Числа должны быть выведены с точностью не хуже 10−6.

 

Примеры
№ Входные данные Выходные данные
1 3
440
220 closer
300 further		 30.0 260.0
2 4
554
880 further
440 closer
622 closer		 531.0 660.0

ID 38583. Две кнопки
Темы: Вывод формулы    Отрезки    Пересечение множеств   

Алиса и Боб управляют роботом. У каждого из них есть по одной кнопке, которая управляет роботом. Алиса начала удерживать кнопку через A секунд после запуска робота и отпустила кнопку  через B секунд после запуска. Боб начал удерживать кнопку через C секунд после запуска и отпустил кнопку через D секунд после запуска. Сколько секунд Алиса и Боб удерживали свои кнопки одновременно?

Входные данные
На вход 4 целых числа: A, B, C и D (\(1<=A<B<=100\), \(1<=C<D<=100\)).

Выходные данные
Выведите продолжительность времени (в секундах), в течение которого Алиса и Боб удерживали свои кнопки одновременно.
 

 

Примеры
№ Входные данные Выходные данные Пояснения
1 0 75 25 100 50 Алиса начала удерживать кнопку через 0 секунд после запуска робота и отпустила ее через 75 секунд после запуска.
Боб начал удерживать кнопку через 25 секунд после запуска и отпустил ее через 100 секунд после запуска.
Следовательно, время, когда они оба удерживали свои кнопки, составляет 50 секунд от 25 секунд после запуска до 75 секунд после запуска.
2 0 33 66 99 0 Алиса и Боб не удерживали кнопки одновременно, поэтому ответ - ноль секунд.
3 10 90 20 80 60  

 
ID 37669. Метро
Темы: Пересечение множеств    Пересечение множеств   

На некоторых кросс-платформенных станциях метро (как, например, "Третьяковская") на разные стороны платформы приходят поезда разных направлений. Таня договорилась встретиться с подругой на такой станции, но поскольку подруга приехала из другого часового пояса, то из-за джетлага сильно проспала, и Тане пришлось долго её ждать. Поезда всегда ходят точно по расписанию, и Таня знает, что поезд стоит на платформе ровно одну минуту, а интервал между поездами (время, в течение которого поезда у платформы нет) составляет a минут для поездов на первом пути и b минут для поездов на втором пути. То есть на первый путь приезжает поезд и стоит одну минуту, затем в течение a минут поезда у платформы нет, затем в течение одной минуты у платформы стоит следующий поезд и т. д.

Пока Таня стояла на платформе, она насчитала n поездов на первом пути и m поездов на втором пути. Определите минимальное и максимальное время, которое Таня могла провести на платформе, или сообщите, что она точно сбилась со счёта.

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

Входные данные
Первая строка входных данных содержит число a - интервал между поездами на первом пути. Вторая строка содержит число b - интервал между поездами на втором пути. Третья строка содержит число n - количество поездов на первом пути, которые увидела Таня. Четвёртая строка
содержит число m - количество поездов на втором пути, которые увидела Таня. Все числа - целые,
от 1 до 1000.

Выходные данные
Программа должна вывести два числа: минимальное и максимальное время в минутах, которое Таня могла стоять на платформе, или одно число -1, если Таня точно ошиблась.
 

Ввод Вывод
1
3
3
2		 5 7
1
5
1
2		 -1

Замечание: В первом примере по первому пути поезда ходят через 1 минуту. По второму - через 3. Стоя на платформе 5, 6 или 7 минут, Таня могла насчитать 3 поезда на первом пути и 2 на втором.
 
ID 37669. Метро
Темы: Пересечение множеств    Пересечение множеств   

На некоторых кросс-платформенных станциях метро (как, например, "Третьяковская") на разные стороны платформы приходят поезда разных направлений. Таня договорилась встретиться с подругой на такой станции, но поскольку подруга приехала из другого часового пояса, то из-за джетлага сильно проспала, и Тане пришлось долго её ждать. Поезда всегда ходят точно по расписанию, и Таня знает, что поезд стоит на платформе ровно одну минуту, а интервал между поездами (время, в течение которого поезда у платформы нет) составляет a минут для поездов на первом пути и b минут для поездов на втором пути. То есть на первый путь приезжает поезд и стоит одну минуту, затем в течение a минут поезда у платформы нет, затем в течение одной минуты у платформы стоит следующий поезд и т. д.

Пока Таня стояла на платформе, она насчитала n поездов на первом пути и m поездов на втором пути. Определите минимальное и максимальное время, которое Таня могла провести на платформе, или сообщите, что она точно сбилась со счёта.

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

Входные данные
Первая строка входных данных содержит число a - интервал между поездами на первом пути. Вторая строка содержит число b - интервал между поездами на втором пути. Третья строка содержит число n - количество поездов на первом пути, которые увидела Таня. Четвёртая строка
содержит число m - количество поездов на втором пути, которые увидела Таня. Все числа - целые,
от 1 до 1000.

Выходные данные
Программа должна вывести два числа: минимальное и максимальное время в минутах, которое Таня могла стоять на платформе, или одно число -1, если Таня точно ошиблась.
 

Ввод Вывод
1
3
3
2		 5 7
1
5
1
2		 -1

Замечание: В первом примере по первому пути поезда ходят через 1 минуту. По второму - через 3. Стоя на платформе 5, 6 или 7 минут, Таня могла насчитать 3 поезда на первом пути и 2 на втором.
 
ID 46436. Прогулка котов
Темы: Пересечение множеств    Отрезки   

Вдоль прямой улицы через каждый метр расположены фонарные столбы. На каждом столбе написан номер метра, на котором он расположен. Первый столб расположен в начале улицы и имеет номер 0. 

Код Рудольф гуляет вдоль улицы, от фонаря с номером a до фонаря с номером b. Полосатый кот Ихмиллион прогуливается от фонаря с номером c до фонаря с номером d. Определите, количество фонарных столбов, мимо которых проходя оба кота.



Входные данные
Вводятся четыре числа в одной строке через пробел: a, b, c, d (0 < a, b, c, d <= 100). 

Выходные данные
Выведите ответ на задачу.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 5 8 6 2 2 Рудольф прогуливается от фонаря с номером 5 до  8-го фонаря и обратно, а Ихмиллион со 6-го по 2-й и обратно. Одновременно оба кота прогуливаются мимо фонарей с номерами 5 и 6. Всего фонарей два.
2 5 3 7 9 0 Нет общих фонарей, мимо которых прогуливаются оба кота.

ID 50539. Прогулка котов
Темы: Пересечение множеств    Отрезки   

Вдоль прямой улицы через каждый метр расположены фонарные столбы. На каждом столбе написан номер метра, на котором он расположен. Первый столб расположен в начале улицы и имеет номер 0. 

Код Рудольф гуляет вдоль улицы, от фонаря с номером a до фонаря с номером b. Полосатый кот Ихмиллион прогуливается от фонаря с номером c до фонаря с номером d. Определите, количество фонарных столбов, мимо которых проходя оба кота.



Входные данные
Вводятся четыре числа в одной строке через пробел: a, b, c, d (0 < a, b, c, d <= 100). 

Выходные данные
Выведите ответ на задачу.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 5 8 6 2 2 Рудольф прогуливается от фонаря с номером 5 до  8-го фонаря и обратно, а Ихмиллион со 6-го по 2-й и обратно. Одновременно оба кота прогуливаются мимо фонарей с номерами 5 и 6. Всего фонарей два.
2 5 3 7 9 0 Нет общих фонарей, мимо которых прогуливаются оба кота.