Мартовские КИТы - 2024 |
Старт: 29.мар.2024 в 16:00:00
Финиш: 29.мар.2024 в 18:00:00
Турнир завершён!
• Турнирная таблица
|
|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
tramway1
Петербургская традиция - цветные маршрутные огни на трамваях,
позволяющие издали определить, какой трамвай приближается.
Те, кто часто ездит трамваем, знают: два зелёных - №7,
красный и синий - №55, синий и красный - №63. Некоторые сочетания
огней повторяются: например, два зелёных и у трамваев №40 и №41 -
но эти маршруты проходят в разных районах и не пересекаются.
Когда управлять городским электротранспортом начал Семён Сидорович
Синёв, он решил оптимизировать систему сигнальных огней: сделать
так, чтобы как можно больше маршрутов несли на себе самое красивое,
по мнению Синёва, сочетание: два синих огня. Но по правилам
одинаковые сигнальные огни могут быть только у маршрутов, не
имеющих общих остановок.
Разработайте программу, которая описанию трамвайных маршрутов
определит максимальное количество маршрутов, по которим можно
пустить "синеглазые" трамваи.
Входные данные. В первой строке - натуральное число N,
количество трамвайных маршрутов (их не более 100). Далее следуют N
строк с описаниями маршрутов: в строке перечислены через пробел
идентификаторы (натуральные числа не больше 1000) остановок,
через которые проходит маршрут. Число остановок на одном
трамвайном маршруте не превышает 100.
Выходные данные. Натуральное число - максимальное количество
маршрутов, которым можно присвоить одинаковое сочетание сигнальных
огней. Известно, что это значение -
в пределах разумной реальности (не больше дюжины).
Для отправки решений необходимо выполнить вход.
|