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

Уральская региональная командная олимпиада по программированию 2015

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

J. Фруктовые коктейли

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Заходят как-то n Дэнчиков в бар, и каждый заказывает по коктейлю из фруктовых соков.
В каждом коктейле может быть от 1 до 3 различных сортов соков. В баре есть три сорта: яблочный, банановый и ананасовый. У каждого Дэнчика есть свой любимый вид коктейля. Коктейль однозначно задаётся тем, какие сорта соков в него входят. Разумеется, каждый Дэнчик заказал по одному своему любимому коктейлю.
Бармен может выставить все n бокалов в один длинный ряд и наливать сок в отрезок последовательных стаканов. Бар очень популярен, поэтому бармен хочет обслужить Дэнчиков как можно быстрее. Для этого он хочет расставить бокалы в таком порядке, что количество «наливаний» будет минимально. За одно «наливание» можно налить один сорт сока в отрезок последовательных стаканов.
Как известно, плотность яблочного сока выше, чем плотность бананового, а плотность бананового выше, чем плотность ананасового. Поэтому, чтобы соки в коктейле не смешивались, следует сначала наливать яблочный, затем банановый, и только в конце ананасовый. Естественно, наливать в каждый бокал нужно только те соки, которые входят в соответствующий коктейль, однако их относительный порядок должен оставаться неизменным.
Дэнчиков слишком много, поэтому бармен сам не может понять, в каком порядке ему следует расставить бокалы. А можете ли вы?

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

В первой строке вводится целое число n (1 ≤ n ≤ 105).
Затем в n строках описаны заказы Дэнчиков. Каждый заказ описывается одной строкой длины от 1 до 3 из заглавных латинских букв A, B, P. В i-й строке перечислены сорта соков, входящих в i-й заказ (A = Apple = Яблочный, B = Banana = Банановый, P = Pineapple = Ананасовый). Буквы внутри строки следуют именно в таком порядке, то есть строка получается из строки "ABP" вычёркиванием некоторого (возможно, нулевого) числа букв.

Результат

В первой строке выведите минимальное количество «наливаний».
Во второй строке выведите номера бокалов в том порядке, в котором их нужно расставить в ряд. Считайте, что заказы и соответствующие им бокалы пронумерованы от 1 до n в том порядке, в котором они даны на входе.
Если оптимальных расстановок несколько, выведите любую.

Пример

исходные данныерезультат
3
A
B
ABP
3
1 3 2 
Автор задачи: Михаил Рубинчик (подготовка — Николай Пермяков, Алексей Данилюк)
Источник задачи: Уральская региональная командная олимпиада по программированию 2015
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2071. Фруктовые коктейли