ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

УрКОП 2020

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Идеальный отряд

Ограничение времени: 0.5 секунды
Ограничение памяти: 256 МБ
Как известно, идеальный отряд состоит из война, мага, клирика и разбойника. Однако иногда приходится обходиться меньшим: войн, маг и клирик могут образовать отряд из трёх человек, который будет не идеальным. Можно составить отряд и из одного война, если больше некуда деваться.
В вашей гильдии состоит n человек. Каждый человек обладает набором квалификаций: он может быть воином, магом, клириком и/или разбойником. А именно, человек обладает любым непустым подмножеством квалификаций, то есть, он может иметь произвольный набор из одной, двух, трёх или четырёх квалификаций.
Чтобы собрать отряд, нужно взять до четырёх человек и дать каждому роль, соответствующую одной из его квалификаций. На каждую роль можно назначить не более одного человека, и одному человеку нельзя дать две роли сразу, даже если он обладает несколькими квалификациями. Таким образом, в отряде будет не более одного человека в роли война, не более одного человека в роли мага и т.д., и всего будет занято ролей столько, сколько человек в отряде.
Вам нужно собрать один отряд наибольшего размера, и если этот отряд не идеален — разместить объявление о приёме новых людей в гильдию. Чтобы составить объявление, требуется для каждой из четырёх квалификаций выяснить, увеличится ли максимальный возможный размер отряда, если нанять человека только с этой квалификацией.

Исходные данные

В первой строке дано единственное целое число n — количество людей в гильдии (1 ≤ n ≤ 15).
Каждая из следующих n строк содержит от 1 до 4 заглавных букв W (Воин), M (Маг), C (Клирик), R (Разбойник), не разделённых пробелом, обозначающих набор квалификаций очередного человека. Буквы будут идти именно в таком порядке, то есть каждая из этих строк получается из строки WMCR удалением не более трёх букв.

Результат

В первой строке выведите единственное число — наибольший размер отряда, который можно собрать.
Если наибольший размер отряда меньше 4, выведите ещё одну строку, начинающуюся с «Looking for», где далее через пробел перечислены квалификации в объявлении. Каждая квалификация — это одно из четырёх слов: «warrior» (Воин), «mage» (Маг), «cleric» (Клирик) или «rogue» (Разбойник), именно в таком порядке. Указывать нужно такие квалификации, что при найме одного человека с только одной из этих квалификаций наибольший размер отряда увеличится.

Примеры

исходные данныерезультат
1
W
1
Looking for mage cleric rogue
2
M
CR
2
Looking for warrior cleric rogue
4
WMCR
WMCR
WMCR
WMCR
4
1
WMCR
1
Looking for warrior mage cleric rogue
Автор задачи: Валентин Зуев
Источник задачи: Уральская командная олимпиада по программированию 2020
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2153. Идеальный отряд