- Описание
- Отправленные решения
115. Современники
Группа людей называется современниками, если был такой момент, когда они могли собраться все вместе и обсуждать какой-нибудь важный вопрос. Для этого в тот момент, когда они собрались, каждому из них должно было уже исполниться 18 лет, но еще не исполниться 80 лет.
Вам дан список великих людей с датами их жизни. Выведите всевозможные максимальные множества современников. Множество современников будем называть максимальным, если нет другого множества современников, которое включает в себя всех людей из первого множества.
Будем считать, что в день своего 18-летия человек уже может принимать участие в такого рода собраниях, а в день 80-летия, равно как и в день своей смерти, — нет.
Формат ввода
Сначала на вход программы поступает число N — количество людей (1 $\le$ N $\le$ 10000). Далее в N строках вводится по шесть чисел — первые три задают дату (день, месяц, год) рождения, следующие три — дату смерти (она всегда не ранее даты рождения). День (в зависимости от месяца, а в феврале — еще и года) от 1 до 28, 29, 30 или 31, месяц — от 1 до 12, год — от 1 до 2005.
Формат вывода
Программа должна вывести все максимальные множества современников. Каждое множество должно быть записано на отдельной строке и содержать номера людей (люди во входных данных нумеруются в порядке их задания, начиная с 1). Номера людей должны разделяться пробелами.
Никакое множество не должно быть указано дважды.
Если нет ни одного непустого максимального множества, выведите одно число 0.
Гарантируется, что входные данные будут таковы, что размер выходных данных для правильного ответа не превысит 2 Мб.
Ограничения
Ограничение времени
3 с
Ограничение памяти
64 МБ
Пример 1
3
2 5 1988 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
2
3
Пример 2
3
2 5 1968 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
2
1 3
Пример 3
3
2 5 1988 13 11 2005
1 1 1 1 1 10
2 1 1910 1 1 1928
0