21/11/2024 21:36:43

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

275. DVD-диски

Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Женя очень любит смотреть интересные фильмы. Недавно его любящий дядя передал ему коллекцию DVD-дисков, но с одним условием. Он потребовал, чтобы Женя смотрел его фильмы с хронологическом порядке. А именно, если фильм `A` был выпущен в году `Y_A`, а фильм `B` — в году `Y_B`, причем `Y_A\ <\ Y_B`, и Женя собирается посмотреть их оба, то он должен просмотреть фильм `A` до фильма `B`. Фильмы, выпущенные в один и тот же год, могут быть просмотрены в любом порядке.

Женя уже был готов начать смотреть фильмы, но неожиданно обнаружилась маленькая проблема: современные DVD-диски используют механизм, известный как региональная защита. Весь мир поделен на пять частей (регионов), и каждый диск может быть просмотрен только в том регионе, для которого он произведен. Поскольку DVD-плееры экспортируются в разные регионы мира, то после того, как пользователь покупает плеер и первый раз включает его, то он должен выбрать регион, в котором он живет. Для того, чтобы дать возможность исправить возможные ошибки в выборе, этот регион может быть изменен. Для того, чтобы предотвратить изменение региона плеера перед просмотром каждого фильма, число таких изменений ограничено пятью.

У Жени есть всего один плеер и огромное желание просмотреть как можно больше фильмов. Исходно его плеер не имеет никакой настройки региона, так что при первом просмотре владелец должен такой регион выбрать. После этого выбранный регион может быть изменен не более пяти раз.

Ваша задача — определить, какие фильмы и в каком порядке должен просмотреть Женя, так чтобы их количество было бы максимальным.

Первая строка входного файла содержит число `N` — общее количество фильмов (`1\ ≤\ N\ ≤\ 2000`). В последующих `N` строках заданы описания фильмов: название фильма в двойных кавычках, год выпуска и номер региона. Длины названий фильмов не превосходят 100, года выпуска представляют собой целые числа от 1870 до 2004 включительно, а номера регионов — числа от 1 до 5.

В первую строку выходного файла следует вывести число `M` — максимальное количество фильмов, которое сможет просмотреть Женя, а в последующих `M` строках названия этих фильмов, в том порядке, в котором Женя должен их просмотреть.

Пример ввода

10
"Gone with the Wind" 1960 1
"The World and the War" 1991 5
"Back to the Future" 1980 1
"The Wall" 1980 2
"Titanic" 1997 3
"Hell on Earth" 1980 3
"Princess" 1980 4
"Yesterday" 1980 5
"Shadows of the Triumph" 1984 3
"Help" 1965 2

Пример вывода

9
"Gone with the Wind"
"Help"
"The Wall"
"Princess"
"Yesterday"
"Back to the Future"
"Hell on Earth"
"Shadows of the Triumph"
"Titanic"

Источник: http://neerc.ifmo.ru/school/archive/

02/07/2007	Лето 2007 дорешивание (11G)
25/07/2007	Лето 2007 - 11 (G)
25/10/2008	Занятие 6 (F)