images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
25/04/2024 19:29:15

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

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2041. Пиццерия

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

Создатели Великобинарии заложили в виртуальных жителей любовь к пицце, но их пицца выглядит как последовательность букв, составляющих название пиццы. Для изготовления пиццы "Маргарита" нужно взять три буквы А, две буквы Р и по одной букве М, Г, И и Т.
Бинарец Кибибайт работает в пиццерии и должен собирать пиццы из поступающих по конвейеру букв-ингредиентов. В каждый момент времени может собираться только одна пицца, название которой выбирает Кибибайт перед началом работы или после сборки очередной пиццы. С конвейера можно брать только тот ингредиент, который проходит в текущий момент мимо Кибибайта. Кибибайт знает несколько названий-рецептов и последовательность поступающих букв и хочет собрать как можно больше пицц, чтобы стать работником месяца и получить повышение.
Формат ввода
Первая строка ввода содержит одно целое число: количество названий `N` (`1\ ≤\ N\ ≤\ 1000`). Далее следует `N` строк, содержащих названия. Названия имеют длину от 1 до 100 букв и состоят только из русских прописных букв от А до Я (буквы с кодами от 192 до 223, без буквы Ё). Далее следует строка длиной от 1 до `100\ 000` букв, состоящая из русских прописных букв — поступающие по конвейеру буквы-ингредиенты.
Формат вывода
В первой строке вывести одно целое число `K` – максимальное количество пицц, которое может собрать Кибибайт. Во второй строке вывести `K` целых чисел — номера рецептов. Если существует несколько вариантов с максимальным количеством, то можно вывести любой из них.

Пример ввода

3
МАРГАРИТА
СРЕДИЗЕМНОМОРСКАЯ
ЛУКОВАЯ
МАРГАРИТАЯАВОКУЛРЕДИСЗЕМЛЯТАРАКАНГОРЧИЦА

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

3
1 3 1
Пояснение:
Когда по конвейеру пройдет последний символ строки, рабочий день Кибибайта заканчивается.
Куда исчезают неиспользованные буквы-ингредиенты в данной задаче неважно, предположим, что из них собирают пиццы другие работники пиццерии, которые стоят на конвейере после Кибибайта. Но нас интересует только количество пицц, собранных Кибибайтом.
loading